本文着重介绍快速排序算法(quick sort)，快速排序和冒泡排序一样是交换排序的一种，快速排序算法可以看成是对冒泡排序算法的改进算法，其平均时间复杂度在nlog(n),基本上是已知的排序算法中速度最快的一种。
冒泡排序的核心思想是通过一次冒泡交换将最大的元素置换到末尾，通过N-1次这样的冒泡交换，完成对待排序数组的排序。
快速排序的核心思想是通过一个partition(分割)操作，将数组的某一个元素放置到正确的排序位置，接着递归对该元素的左侧和右侧分别进行partition操作，直到所有的元素都放到正确的位置，这样排序就结束了。
下面通过一个图例的方式来介绍对待排序数组的一次partition操作。假设待排序数组int []A = new int[]{5,1,4,7,9,3,2,5}。
一丶快速排序原理
-
随便选取一个元素(后文简称特定元素)，这里选取第一个元素5，目的是将元素5放置到正确的排序位置，让元素5左侧的元素都小于或等于5，右侧的元素都大于5。
-
在partition操作中，维护三个重要成员，left指针指向区间的第一个元素，right指针指向区间的最后一个元素，以及对选中元素额备份。
image
-
移动right指针，right=right-1，一直到A[right]<=5,停止移动移动left指针，left = left+1，一直到A[left]>5停止移动。
image
-
left指针移动和right指针移动结束后，交换left指针和right指针指向的内容。
image
-
继续重复步骤2，3，4
image
image
-
继续重复步骤2，3，4发现left=right,两个指针相遇了，那么结束本次partition操作，让 left和right共同指向的元素去覆盖选中的元素5。
image
image
-
将备份的元素5覆盖left和right共同指向的元素。
image
-
执行完步骤7之后，一次的partion操作就结束了，将数组分割成的两个部分，在指定元素5的左侧，所有的元素都小于或等于5，在指定元素的右侧所有的元素都大于5。对左侧的数组{3，1，4，5，2}和右侧数组{9，7}递归partition操作。递归执行partition函数后，快速排序就完成了，数组也由无序变为了有序的状态了。
二丶快速排序的细节分析
(1)在一次partition操作中，对特定元素的指定一般都取待排序区间中的第一个元素。
(2)left指针和right指针的移动顺序是存在区别的，必须先移动right指针，后移动left指针。试想当left和right指针相遇的时候，若先移动right指针，可以保证最后left和right指向的元素是严格小于或等于被指定元素的。这样在执行步骤7和步骤8之后，可以完全的保证被指定元素放置在合适的位置——左侧的所有元素小于自身，右侧的所有元素大于自身。
(3)快速排序的每一次partition操作，必须输入两个参数——start和end。start代表待排序区间的开始位置，end代表待排序区间的结束位置。
(4)每一次partition操作，必须返回特定元素分割后的位置，用作下一次partition操作的依据。
(5)每次partition操作，如果start>end.则不执行partition流程。
三丶java代码实现
public static void quickSort(int [] num,intstart,int end){
if(start>end)
return ;
int mid = partition(num,start,end);
quickSort(num,start,mid-1);
quickSort(num,mid+1,end);
}
public static int partition(int[] num,int start,int end){
int copy = num[start];
int left = start;
int right = end;
while(left<right){
while(left<right&&num[right]>copy){
right = right -1;
}
while(left<right&&num[left]<=copy){
left++;
}
int temp = num[left];
num[left] = num[right];
num[right] =temp;
}
num[start] = num[left];
num[left] = copy;
return left;
}
Referecne:
[1] 数据结构与算法 java语言描述版
[2] 原文博客链接
网友评论