
快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序。使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好。就平均时间而言,是目前被认为最好的一种内部排序方法
基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指针和第三个指针分别为left指针和right指针,分别指向最左边的值和最右边的值。left指针和right指针从两边同时向中间逼近,在逼近的过程中不停的与枢轴比较,将比枢轴小的元素移到低端,将比枢轴大的元素移到高端,枢轴选定后永远不变,最终在中间,前小后大。
需要两个函数:
① 递归函数 public static void quickSort(int[] array, int left, int right) {}
② 分割函数(一趟快速排序函数)public static int partitionByPivotValue(int[] array, int left, int right) {}
package lsg.ap.quick; import java.util.Random; public class QuickSort { /** * 先按照数组为数据原型写出算法,再写出扩展性算法。数组 * 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比 另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序 过程可以递归进行,以此达到整个数据变成有序序列。 */ public static void quickSort(int[] array, int left, int right) { int pivotKey; if (left < right) { pivotKey = partitionByPivotValue(array, left, right); // 对左右数组递归调用快速排序,直到顺序完全正确 quickSort(array, left, pivotKey - 1); quickSort(array, pivotKey + 1, right); } } /** * pivotValue作为枢轴,较之小的元素排序后在其左,较之大的元素排序后在其右 * * @param array * @param left * @param right * @return */ public static int partitionByPivotValue(int[] array, int left, int right) { int pivotValue = array[left];//提前把枢轴值取出,防止后面移动元素时元素被覆盖导致丢失 // 枢轴选定后永远不变,最终在中间,前小后大 while (left < right) { while (left < right && array[right] >= pivotValue) { --right; } //while循环的作用就是一直到 array[right] < pivotValue跳出 // 将比枢轴小的元素移到低端,此时right位相当于空,等待低位比pivotkey大的数补上 array[left] = array[right];//array[left]枢值已经被第一句提前取出保存了 while (left < right && array[left] <= pivotValue) { ++left; }//while循环的作用就是一直到 array[right] > pivotValue跳出 // 将比枢轴大的元素移到高端,此时left位相当于空,等待高位比pivotkey小的数补上 array[right] = array[left]; } // 当left == right,完成一趟快速排序,此时left位相当于空,等待pivotkey补上 array[left] = pivotValue; return left; } /** * * 输出相应数组的结果 * @param array */ private static void printArray(int[] array) { for(int value:array) System.out.print(" "+value+" "); System.out.println(); } public static void main(String[] args) { // TODO Auto-generated method stub //小数据量的测试 int[] array=new int[]{8,3,2,1,7,4,6,5}; //下面是大数据量的测试。这样才能看出不同算法的优劣 Random random=new Random(); int[] array2=new int[2000]; for(int j=0;j<2000;j++) { array2[j]=random.nextInt(100000); } //输出原数组的内容 System.out.println("排序前数组元素为:"); printArray(array); long dateStart=System.nanoTime(); //归并排序操作 quickSort(array,0,array.length-1); long dateEnd= System.nanoTime(); long totalTime=dateEnd-dateStart; System.out.println("快速排序的时间复杂度为:"); System.out.println(totalTime+"纳秒"); //输出排序后的相关结果 System.out.println("排序后数组元素为:"); printArray(array); } }