算法系列之快速排序最佳实践你知道吗

1.原理

快速排序采用"分而治之递归排序"的思想，对于一组数据，选择一个基准元素（base），比如选择第一个、中间位置元素或最后一个元素，通过第一轮扫描，比base小的元素都在base左边，比base大的元素都在base右边，然后再用同样的方法递归排序数组的左右两个子部分，直到序列中所有数据均有序为止。

2.代码

以下使用Java代码作为示例：

//测试快速排序的函数
public void testQuickSort(){
	//进行排序的数组样例
	int[] data = new int[]{80, 2, 67, 32, 57, 13, 48, 1, 60, 100};
    quickSort(data,0,data.length-1);
}

/**
快速排序主函数
arr：要排序的数组
left：排序数组左边界索引
right：排序数组右边界索引
*/
public void quickSort(int arr[], int left, int right) {
    if (left < right) {
        //算出基准元素索引值index
        int index = partition(arr, left, right);
        //对低于index索引的数组递归排序
        quickSort(arr, left, index - 1);
        //对高于index索引的数组递归排序
        quickSort(arr, index + 1, right);
    }

}

//算出基准元素索引值，此索引值左侧值都小于基准元素值，此索引值右侧值都大于基准元素值
public int partition(int[] num, int left, int right) {
    if (num == null || num.length <= 0 || left < 0 || right >= num.length) {
        return 0;
    }
	//获取数组基准元素的下标
    int prio = num[left + (right - left) / 2]; 
	//从两端交替向中间扫描	
    while (left <= right) {                 
        while (num[left] < prio)
            left++;
        while (num[right] > prio)
            right--;
        if (left <= right) {
			//将不符合条件的元素值交换位置并继续扫描
            swap(num, left, right);        
            left++;
            right--;
        }
    }
    return left;
}

//交换元素
public void swap(int[] num, int left, int right) {
    int temp = num[left];
    num[left] = num[right];
    num[right] = temp;
}

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。