首页 > 代码库 > 对快速排序的一点小探究
对快速排序的一点小探究
快速排序算法是一种划分交换的方法，采用了分治法进行排序。
1 public static void quikSort(int a[],int left,int right)2 {3 if(left >= right)return;4 int p = partition(a,left,right);5 quikSort(a,left,p-1);6 quikSort(a,p+1,right);7 }
开始，快速排序中划分方法partition（）的基准元素都选取为最左侧 left 处的值：
1 public static int partition(int a[],int left,int right) 2 { 3 int index = left; 4 int value = http://www.mamicode.com/a[index];//基准元素 5 while(left < right) 6 { 7 //比较中带等号，针对重复元素如：4，3，4，检测指针才会移动，不然就死循环了 8 while(left < right && a[right] >= value) 9 {10 right--;11 }12 a[left] = a[right];13 // if(left < right)14 // {15 // //需要比较一次left和right是否重合。虽然可以避免了它自己的值与自己比较，但是多了一次判断比较；效果上没有改进16 // left++;17 // }18 //left++;//直接动left指针就是错误。当left与right指针重合时，这句话执行就不对，强制的多加了一次！重合之前都是对的19 while(left < right && a[left] <= value)20 {21 left++;22 }23 a[right] = a[left];24 }25 //跳出循环必然是left==right了,left和right重合就找到了基准元素就位时的位置26 a[left] = value;27 //System.out.println(" 划分点(该元素最终位置)： " + left);28 return left;29 }
后来，想到使用随机值，在某些程度上（比如在基本已经有序的情况下）改进快速排序(以下代码执行结果是错误的)，如下：
1 public static int partition2(int a[],int left,int right) 2 { 3 4 int index = left + r.nextInt(right - left + 1);//随机选基准元素 5 int value = http://www.mamicode.com/a[index];//用value保存了当前选取的枢轴元素，就可腾空一个位置 6 while(left < right) 7 { 8 //比较中带等号，针对重复元素如：4，3，4，检测指针才会移动，不然就死循环了 9 10 //先让右侧开始检测，对于4,9；选了9当value，直接开始right--就不对11 while(left < right && a[right] >= value)12 {13 right--;14 }15 a[index] = a[right];16 index = right;17 while(left < right && a[left] <= value)18 {19 left++;20 }21 a[right] = a[left];22 index = left;23 }24 a[left] = value;25 return left;26 }
结果思考，得知以上代码错误的原因：一定要把基准元素交换至最左边或最右边（放到最左就从right开始检测，最右就应该从left开始检测），使得腾空的位置从最边上位置，分别从最左最右两个方向，向基准元素就位的真正位置逼近，而不是一开始就从枢轴元素的原始位置index开始移动。
修改代码如下即可：
1 public static int partition(int a[],int left,int right) 2 { 3 4 int index = left + r.nextInt(right - left + 1);//随机选基准 5 int value =http://www.mamicode.com/ a[index];
6 //交换随即选取的基准元素至最左侧left处；并且就必须要先从right开始检测；如【4,9,4】，假如选取了a[0] = 4为基准元素，又从left开始检测就错误了。 7 int temp = a[left]; 8 a[left] = a[index]; 9 a[index] = temp;10 11 while(left < right)12 {13 14 while(left < right && a[right] >= value)15 {16 right--;17 }
a[left] = a[right];18 while(left < right && a[left] <= value)19 {20 left++;21 }22 a[right] = a[left];23 }24 a[left] = value;25 return left;26 }
另一种划分函数的实现方式，从一个方向确定基准元素的最终位置（每次发现一个比基准元素小的元素，就通过使用index挨个从最前往后放。从前往后统统扫描一遍，把所有小于value的都放前面了，自然大于value的都在后面）：
1 public static int partition(int a[],int left,int right) 2 { 3 int index = left; 4 int value =http://www.mamicode.com/ a[left]; 5 //从左端向右端一直检测 6 for(int i=left+1;i<=right;i++) 7 { 8 if(a[i] < value) 9 {10 index++;11 if(index != i)12 {13 swap(a[i],a[index]);14 }15 } 16 } 17 a[left] = a[index];18 a[index] = value;//基准元素就位19 20 return index; 21 }
总结：快速排序定位轴的位置，关键就看你是怎么做到，小于枢轴元素（基准元素）值的放到枢轴左边，大于枢轴元素值的放到枢轴右边；用腾空一个位置的办法也好，用swap的想法也好，都是如此。
扩展思考：
一、考虑使用双向链表，设置头指针和尾指针，与基准元素值进行比较后，（拔下结点）在头结点之前插入小的，在尾结点之后插入大的。
二、排序的改进算法：（序列长度在5~25时）采用直接插入排序对划分后的子序列排序进行排序。
对快速排序的一点小探究
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。