快速排序

###算法过程
快速排序 的思想很简单，整个排序过程只需要三步：

  1. 在数据集之中，找一个基准点；
  2. 建立两个数组，分别存储左边和右边的数组；
  3. 利用递归进行下次比较。

Java代码

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
31
32
33
34
35
public class QuickSort {    //一次划分
    public static int partition(int[] arr, int left, int right) {
        int pivotKey = arr[left];
        int pivotPointer = left;

        while(left < right) {
            while(left < right && arr[right] >= pivotKey)
                right --;
            while(left < right && arr[left] <= pivotKey)
                left ++;
            swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
        }
        swap(arr, pivotPointer, left); //最后把pivot交换到中间
        return left;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right)
            return ;
        int pivotPos = partition(arr, left, right);
        quickSort(arr, left, pivotPos-1);
        quickSort(arr, pivotPos+1, right);
    }
    public static void sort(int[] arr) {
        if(arr == null || arr.length == 0)
            return ;
        quickSort(arr, 0, arr.length-1);
    }

    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
}

C代码

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
int Division(int a[],int left, int right) //分割
{
    int base=a[left];    //基准元素
    while(left<right)
    {
        while(left<right && a[right]>base)
            --right;     //从右向左找第一个比基准小的元素
        a[left]=a[right];
        while(left<right && a[left]<base )
            ++left;      //从左向右找第一个比基准大的元素
        a[right]=a[left];
    }
    a[left]=base;
    return left;
}
void QuickSort(int a[],int left,int right)
{
    int i,j;
    if(left<right)
    {
        i=Division(a,left,right);   //分割
        QuickSort(a,left,i-1);     //将两部分分别排序
        QuickSort(a,i+1,right);
    }
}

JavaScript代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr){
	if(arr.length<=1){
		return arr;//如果数组只有一个数，就直接返回；
	}

	var num = Math.floor(arr.length/2);//找到中间数的索引值，如果是浮点数，则向下取整
	var numValue = arr.splice(num,1);//找到中间数的值
	var left = [];
	var right = [];

	for(var i=0;i<arr.length;i++){
		if(arr[i]<numValue){
			left.push(arr[i]);//基准点的左边的数传到左边数组
		}
		else{
			right.push(arr[i]);//基准点的右边的数传到右边数组
		}
	}
	return quickSort(left).concat(numValue,quickSort(right));//递归不断重复比较
}
alert(quickSort([32,45,37,16,2,87]));//弹出“2,16,32,37,45,87”

Python代码

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
#!/usr/bin/python
# -*- coding: utf-8 -*-
def sub_sort(array,low,high):
    key = array[low]
    while low < high:
        while low < high and array[high] >= key:
            high -= 1
        while low < high and array[high] < key:
            array[low] = array[high]
            low += 1
            array[high] = array[low]
    array[low] = key
    return low

def quick_sort(array,low,high):
     if low < high:
        key_index = sub_sort(array,low,high)
        quick_sort(array,low,key_index)
        quick_sort(array,key_index+1,high)

if __name__ == '__main__':
    array = [8,10,9,6,4,16,5,13,26,18,2,45,34,23,1,7,3]
    print array
    quick_sort(array,0,len(array)-1)
    print array

R代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
qsort <- function(v) {
  if ( length(v) > 1 )
  {
    pivot <- (min(v) + max(v))/2.0                            
    c(qsort(v[v < pivot]), v[v == pivot], qsort(v[v > pivot]))
  } else v
}

N <- 100
vs <- runif(N)
system.time(u <- qsort(vs))
print(u)

Qsort <- function(x){
 if (length(x) < 2) return(x)
 return(c(Qsort(x[x<x[1]]), x[x==x[1]], Qsort(x[x>x[1]])))
}
赏

本文地址： http://easonlv.github.io/2016/09/25/Implemention-of-QuickSork/