做淘宝店铺有哪些好的网站,东莞网站制作建设收费,建设工程施工合同2017,龙岩网站定制快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为#xff1a; 从序列中挑出一个元素#xff0c;作为基准(pivot). 把所有比基准值小的元素放在基准前面#xff0c;所有比基准值大的元素放在基准的后面#xff08;相同的数可以到任…快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为 从序列中挑出一个元素作为基准(pivot). 把所有比基准值小的元素放在基准前面所有比基准值大的元素放在基准的后面相同的数可以到任一边这个称为分区(partition)操作。 对每个分区递归地进行步骤1~3递归的结束条件是序列的大小是0或1这时整体已经被排好序了。 快速排序是对冒泡排序的一种改进 快速排序的代码如下 public static void quickSort(int[] numbers,int low,int high) {if(low high) {int middle getMiddle(numbers,low,high); quickSort(numbers, low, middle-1); quickSort(numbers, middle1, high); }} public static int getMiddle(int[] numbers, int low,int high) {int temp numbers[low]; while(low high){//高位判断 while (low high numbers[high] temp) {high--;}numbers[low] numbers[high]; // 否则情况 numbers[high] temp 交换位置//低位判断while (low high numbers[low] temp) {low;}numbers[high] numbers[low]; // 否则情况 numbers[low] temp 交换位置}numbers[low] temp ; return low ;} 备注 可以采用空位法来梳理整个过程 比如数组ss{4,5,7,8,6,3} temp ss[0] 4 ; 排序开始可以认为数组为{[],5,7,8,6,3} 首位被空出来以空位代替。 1与高位比较有两种情况 1.比较位上的数比temp大 此时符合数组比较规律则数组下标自减。 2.比较位上的数比temp小 则将比较位上的数放入空位。 由于 temp 4 ss[5] 3将 ss[5] 放入空位于是数组变成{3,5,7,8,6,[]}可以认为被交换位置 ss[5] 被空出来。 2与低位比较也有两种情况与高位类似。 1.比较位上的数比temp小 此时符合数组比较规律则数组下标自增。 由于ss[0] 3 temp 4 ,数组下标自增1到ss[1],{3,5,7,8,6,[]}此时ss[1] 5 temp 4不再符合该判断条件! 2.比较位上的数比temp大 则将比较位上的数放入空位。 由于 ss[1] 5 temp 4 则将ss[1]放入空位。此时的数组排列为{3,[],7,8,6,5}。 在大while循环条件下重复以上操作最终的数组排列为{3,[],7,8,6,5}。 将temp的值注入其中的空位数组的排列为{3,4,7,8,6,5}。 递归以上,可以将之看做为{3},4,{7,8,6,5} 可得到最终排序结果。 扩展关于快速排序与归并排序之比较 归并排序和快速排序都使用了分治法。 对于归并排序大量的工作是将两个子线性表进行归并归并是在子线性表都排好序之后进行的。 对于快速排序大量的工作是将线性表划分为两个子线性表划分是在子线性表排好序前进行的。 在最差情况下归并排序的效率高于快速排序但是在平均情况下两者效率相同O(NlogN)。 归并排序在归并两个子数组时需要一个临时数组而快速排序不需要额外的数组控件因此快速排序的空间效率高于归并排序。 参考文章http://blog.csdn.net/morewindows/article/details/6684558 end 转载于:https://www.cnblogs.com/understander/p/6686372.html
