快速排序

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。平均时间复杂度：O(nlogn)。
其核心思想是让每个数的左边放比它小的数，右边放比它大的数；左右2边分而治之。

C实现快速排序

void quicksoft(int a[],int left,int right)
{
    int i,j,temp;
    i = left;
    j = right;
    temp=a[left];
    if(left >= right)
        return ;
    while(i!=j)
    {
        while(i<j&&a[j]>=temp)
        {
            j--;
        }
        if(i < j)
        {
            a[i] = a[j];
        }
        while(i<j&&a[i]<=temp)
        {
            i++;
        }
        if(i<j)
        {
            a[j]=a[i];
        }
    }
    a[i]=temp;
    quicksoft(a,left,i-1);
    quicksoft(a,i+1,right);
}

java实现快速排序

public void quickSort(int[] arr, int left, int right) {
    if (left > right) {
        return;
    }

    int l = left;
    int r = right;
    int temp = arr[left];

    while (l < r){
        while (l<r && arr[r] >= temp){
            r--;
        }
        if (l < r){
            arr[l] = arr[r];
        }

        while (l<r && arr[l] <= temp){
            l++;
        }
        if(l<r){
            arr[r] = arr[l];
        }
    }
    arr[l] = temp;
    quickSort(arr, left, l-1);
    quickSort(arr, l+1, right);
}

Golang实现快速排序

实现方案一：

func quickSort(arr *[6]int, left int, right int) {
	if left >= right {
		return
	}

	l := left
	r := right
	tmp := arr[left]

	for l != r {

		for l < r && arr[r] >= tmp {
			r--
		}
		if l < r {
			arr[l] = arr[r]
		}

		for l < r && arr[l] <= tmp {
			l++
		}
		if l < r {
			arr[r] = arr[l]
		}
	}
	arr[l] = tmp
	quickSort(arr, left, l-1)
	quickSort(arr, l+1, right)
}

实现方案二：

func quickSort(arr *[6]int, left int, right int) {

	l := left
	r := right

	midIndex := (left + right) / 2
	pivot := arr[midIndex]

	// 循环完成后，实现mid左边的数都比其小，右边的数都比其大
	for l < r {

		// 找到左边比mid大的值
		for arr[l] < pivot {
			l++
		}
		// 找到右边比mid小的值
		for arr[r] > pivot {
			r--
		}

		if l >= r {
			break
		}

		arr[l], arr[r] = arr[r], arr[l]

		if arr[l] == pivot {
			r--
		}
		if arr[r] == pivot {
			l++
		}
	}

	if l == r {
		l++
		r--
	}

	if left < r {
		quickSort(arr, left, r)
	}
	if right > l {
		quickSort(arr, l, right)
	}
}