快速排序(递归)

  |  

  欢迎来到我的博客,这是第一次以这种方式写文章,我的博客主要记录一些关于算法的内容等等。第一篇的话,先来写一下排序里面的快速排序吧O(∩_∩)O。

快速排序

快速排序过程图

JavaScript Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(A,left,right){
let low = left, high = right
if(low>high) return
let key = A[left]
while( left < right ) {
while(left < right && A[right] >= key )
right--
A[left] = A[right]
while(left<right && A[left] <= key)
left++
A[right] = A[left]
}

A[left] = key

quickSort(A,low,left-1)
quickSort(A,left+1,high)
}

data = [1,0,2,9,3,8,4,7,5,6]
quickSort(data,0,data.length-1)

More info: Writing

C Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef int ElemenType;

int partition(ElemenType data[], int left, int right){
ElementType key = data[left];
while( left < right ) {
while(left<right && data[right] >= key)
right--;
data[left] = data[right];
while(left<right && data[left] <= key)
left++;
data[right] = data[left];
}
data[left] = key;
return left;
}

void QuickSort(ElementType data[], int low, int high){
if(low<high){
int index = partition(data,low,high);
QuickSort(data,low,index-1);
QuickSort(data,index+1,high);
}
}

Java Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void QuickSort(int data[], int low, int high){
int left = low;
int right = high;
if(left > right) return;
int key = data[low];
while(low < high){
while(low < high && data[high] >= key)
high--;
data[low] = data[high];
while(low < high && data[low] <= key)
low++;
data[high] = data[low];
}
data[low] = key;

QuickSort(data, left, low-1);
QuickSort(data, low+1, right);
}

public void Solution(int data[]){
QuickSort(data,0,data.length-1);
for(int i=0;i<data.length;i++){
System.out.print(data[i]);
if(i<data.length-1)
System.out.print(" ");
}
}

int temp[] = {1,0,2,9,3,8,4,7,5,6};
Solution(temp);

Python Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quickSort(array,low,high):
if low > high:
return
left = low
right = high
key = array[low]
while low < high:
while low < high and array[high] >= key:
high -= 1
array[low] = array[high]
while low < high and array[low] <= key:
low += 1
array[high] = array[low]
array[low] = key
quickSort(array,left,low-1)
quickSort(array,low+1,right)

if __name__ == '__main__':
temp = [1,0,2,9,3,8,4,6,5,7]
print temp
quickSort(temp,0,len(temp)-1)
print temp

本文标题:快速排序(递归)

文章作者:JarryChen

发布时间:2019年10月24日 - 04:59

最后更新:2019年11月06日 - 00:04

原始链接:https://jarrychen.xyz/archives/57361fba.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。