排序——快速排序（Quick sort）

概况

快速排序（Quick sort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。

算法思路

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

1、首先设定一个分界值，通过该分界值将数组分成左右两部分。

2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

概括来说为 挖坑填数 + 分治法。

图解算法

快速排序主要有三个参数，left 为区间的开始地址，right 为区间的结束地址，Key 为当前的开始的值。

我们从待排序的记录序列中选取一个记录（通常第一个）作为基准元素（称为key）key=arr[left]，然后设置两个变量，left指向数列的最左部，right 指向数据的最右部。

第一步

key 首先与 arr[right] 进行比较，如果 arr[right]key则我们只需要将right--，right--之后，再拿arr[right]与key进行比较，直到arr[right]

第二步

如果右边存在arr[right]key,则将arr[right]=arr[left]，如果arr[left]

第三步

然后再移动right重复上述步骤。

第四步

最后得到 {23 58 13 10 57 62} 65 {106 78 95 85}，再对左子数列与右子数列进行同样的操作。最终得到一个有序的数列。

{23 58 13 10 57 62} 65 {106 78   95 85}

{10 13} 23 {58 57 62} 65 {85 78 95} 106

10 13 23 57 58 62 65 78 85 95 106

动画展示

我们借用五分钟学算法的gif动图，感谢五分钟学算法。

  1. 首先，操作数列中的所有数字
  2. 在所有数字中选择一个数字作为排序的基准（pivot）, pivot 通常是随机选择的，在这里为了演示方便，我们选择最右边的数字作为 pivot
  3. 选取好 pivot 后，在操作数列中选择最左边的数字标记为 左标记 ，最右边的数字标记为 右标记
  4. 将左边的标记向右移动
  5. 当 左标记 达到超过 pivot 的数字时，停止移动
  6. 在这里，8 > 6 ,所以停止移动
  7. 然后将右边的标记向左移动
  8. 当 右标记 达到小于 pivot 的数字时，停止移动
  9. 在这里，4 > 6 ,所以停止移动
  10. 当左右标记停止时，更改标记的数字
  11. 因此，左标记 的作用是找到一个大于 pivot 的数字，右标记 的作用是找到一个小于 pivot 的数字
  12. 通过交换数字，可以在数列的左边收集小于 pivot 的数字集合，右边收集大于 pivot 的数字集合
  13. 交换之后，继续移动 左标记
  14. 在这里，9 > 6 ,所以停止移动
  15. 然后将右边的标记向左移动
  16. 当 右标记 碰撞到 左标记 时也停止移动
  17. 如果左右侧的标记停止时，并且都在同一个位置，将这个数字和 pivot 的数字交换
  18. 这就完成了第一次操作
  19. 小于 6 的都在 6 的左侧，大于 6 的都在 6 的右侧
  20. 然后递归对这分成的两部分都执行同样的操作
  21. 完成 快速排序

算法性能

时间复杂度

理想情况

如果足够理想，那我们期望每次都把数组都分成平均的两个部分，如果按照这样的理想情况分下去，我们最终能得到一个完全二叉树。如果排序 n 个数字，那么这个树的深度就是log2n+1log2n+1，如果我们将比较 n 个数的耗时设置为 T(n)，那我们可以得到如下的公式

  1. T(n) ≤ 2T(n/2) + n，T(1) = 0  
  2. T(n) ≤ 2(2T(n/4)+n/2) + n = 4T(n/4) + 2n  
  3. T(n) ≤ 4(2T(n/8)+n/4) + 2n = 8T(n/8) + 3n  
  4. ......
  5. T(n) ≤ nT(1) + (log2n)×n = O(nlogn)

最坏情况

而在最坏的情况下，这个树是一个完全的斜树，只有左半边或者右半边。这时候我们的比较次数就变为∑n−1i=1(n−i)=(n−1)+(n−2)+⋯+1=n∗(n−1)2=O(n2)∑n−1i=1(n−i)=(n−1)+(n−2)+⋯+1=n∗(n−1)2=O(n2)

空间复杂度

原地排序

原地快排的空间占用是递归造成的栈空间的使用，最好情况下是递归\(log_{2}n\)次，所以空间复杂度为O(long2n)O(long2n)，最坏情况下是递归 n-1 次，所以空间复杂度是O(n)O(n)。

非原地排序

对于非原地排序，每次递归都要声明一个总数为n的额外空间，所以空间复杂度变为原地排序的n倍，即最好情况下O(nlog2n)O(nlog2n)，最差情况下\(O(n^{2})\)。

稳定性

不稳定。

代码实现

C和C++

  1. void QuickSort(int array[], int low, int high) {
  2.     int i = low; 
  3.     int j = high;
  4.     if(i >= j) {
  5.         return;
  6.     }
  7.  
  8.     int temp = array[low];
  9.     while(i != j) {
  10.         while(array[j] >= temp && i < j) {
  11.             j--;
  12.         }
  13. 	while(array[i] <= temp && i < j) {
  14.             i++;
  15.         }
  16. 	if(i < j) {
  17.             swap(array[i], array[j]);
  18.         }
  19.     }
  20.  
  21.     //将基准temp放于自己的位置，（第i个位置）
  22.     swap(array[low], array[i]);
  23.     QuickSort(array, low, i - 1);
  24.     QuickSort(array, i + 1, high);
  25. }

Java

  1. public static int[] qsort(int arr[],int start,int end) {        
  2.     int pivot = arr[start];        
  3.     int i = start;        
  4.     int j = end;        
  5.     while (i
  6.         while ((ipivot)) {                
  7.             j--;            
  8.         }            
  9.         while ((i
  10.             i++;            
  11.         }            
  12.         if ((arr[i]==arr[j])&&(i
  13.             i++;            
  14.         } else {                
  15.             int temp = arr[i];                
  16.             arr[i] = arr[j];                
  17.             arr[j] = temp;            
  18.         }        
  19.     }        
  20.     if (i-1>start) arr=qsort(arr,start,i-1);        
  21.     if (j+11,end);        
  22.     return (arr);    
  23. }

Python

  1. def swap(arr, i, j):
  2.     arr[i], arr[j] = arr[j], arr[i]
  3.  
  4. def partition(arr, left, right):
  5.     pivot = left
  6.     index = pivot+1
  7.     i = index
  8.     while i<=right:
  9.         if arr[i]
  10.             swap(arr, i, index)
  11.             index+=1
  12.         i+=1
  13.     swap(arr, pivot, index-1)
  14.     return index-1
  15.  
  16. def quickSort(arr, left=None, right=None):
  17.     left = 0 if not isinstance(left, (int, float)) else left
  18.     right = len(arr)-1 if not isinstance(right, (int, float)) else right
  19.  
  20.     if left < right:
  21.         partitionIndex = partition(arr, left, right)
  22.         quickSort(arr, left, partitionIndex-1)
  23.         quickSort(arr, partitionIndex+1, right)
  24.     return arr

注：本文转载自blog.csdn.net的努力的老周的文章"https://blog.csdn.net/justidle/article/details/104203963"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！