高级排序:快速排序 博客分类: Sort
程序员文章站
2024-02-04 16:30:58
...
public void quickSort(int[] array){ this.quickSort(array, 0, array.length - 1); } public void quickSort(int[] array,int left,int right){ if(right - left <= 0){ return; }else{ int partition = this.partition(array, left, right); this.quickSort(array, left, partition - 1); this.quickSort(array, partition + 1, right); } } private int partition(int[] array,int left,int right){ int leftScan = left; int rightScan = right - 1; int middle = left + (right - left)/2; if(array[middle] < array[right] && array[middle] > array[left]){ this.swap(array, right, middle); }else if(array[left] < array[right] && array[left] > array[middle]){ this.swap(array, right, left); } int pivot = array[right]; while(true){ for(;leftScan <= right - 1;leftScan++){ if(array[leftScan] > pivot)break; } for(;rightScan >= left;rightScan--){ if(array[rightScan] < pivot)break; } if(leftScan >= rightScan){ break; }else{ this.swap(array, leftScan, rightScan); } } this.swap(array, leftScan, right); return leftScan; } private void swap(int[] array,int index1,int index2){ int temp = array[index2]; array[index2] = array[index1]; array[index1] = temp; }
效率:
快速排序是对冒泡排序的改进,基本思想是选取一个支点,使支点左边全部小于支点,右边全部大于支点.如果支点选择不当,会造成排序极度缓慢(时间复杂度变成O(N^2)),比如选取最后边为支点而数组是逆序的.所以一般采用比较最右端,最左端和中间的元素,选择中间大小的作为支点.时间复杂度为:O(N*logN)
推荐阅读
-
高级排序:快速排序 博客分类: Sort
-
Python 列表的sort()方法之高级排序
-
List之sort、sorted高级排序-Python3.7 And 算法<七>
-
php数据结构与算法(PHP描述) 快速排序 quick sort
-
python sort、sorted高级排序技巧
-
php数据结构与算法(PHP描述) 快速排序 quick sort
-
【数据结构与算法】高级排序(希尔排序、归并排序、快速排序)完整思路,并用代码封装排序函数
-
JS实现高级排序——(希尔排序、快速排序)
-
php数据结构与算法(PHP描述) 快速排序 quick sort_PHP教程
-
PHP排序算法之快速排序(Quick Sort)及其优化算法详解