快速排序是对冒泡排序的一种改进。它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按次
方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2),最好情况时间复杂度为O(nlog2n)。 假设要排序的数组是A[1]……A[N-1],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过 程称为一躺快速排序。一趟快速排序的算法是: 1)设置两个变量I、J,排序开始的时候I:=0,J:=N-1; 2)以第一个数组元素作为关键数据,赋值给X,即X:=A[0]; 3)从J开始向前搜索,找到第一个小于X的值,两者交换,同时设置I:=I+1; 4)从I开始向后搜索,找到第一个大于X的值,两者交换,同时设置J:=J-1; 5)、重复第3、4步,直到I=J; 例如:待排序的数组nums的值分别是: int[] nums = { 4, 1, 5, 3, 2}; 排序的过程是: 第1趟: 2,1,5,3,4, (lo,hi) = (1,4) 2,1,5,3,4, (lo,hi) = (2,4) 2,1,4,3,5, (lo,hi) = (2,3) 2,1,3,4,5, (lo,hi) = (3,3) 此时,数组分成2部分:{2,1,3},4,{5} 第2趟对{2,1,3}排序:过程同第1趟 第3趟对{5}排序:过程同第1趟 以下是java代码实现快速排序的过程: public class Quicksort { public static void main(String[] args) { int[] nums = { 4, 1, 5, 3, 2}; // 应用快速排序方法 quickSort(nums, 0, nums.length - 1); // 显示排序后的数组 for (int i = 0; i < nums.length; ++i) { System.out.print(nums[i] + ","); } } /** 快速排序方法 */ public static void quickSort(int[] a, int lo0, int hi0) { int lo = lo0; int hi = hi0; if (lo >= hi) return; // 确定指针方向的逻辑变量 boolean transfer = true; while (lo != hi) { if (a[lo] > a[hi]) { // 交换数字 int temp = a[lo]; a[lo] = a[hi]; a[hi] = temp; // 决定下标移动,还是上标移动 transfer = (transfer == true) ? false : true; } // 将指针向前或者向后移动 if (transfer) hi--; else lo++; // 显示每一次指针移动的数组数字的变化 for (int i = 0; i < a.length; ++i) { System.out.print(a[i] + ","); } System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")"); System.out.println(""); } // 将数组分开两半,确定每个数字的正确位置 lo--; hi++; quickSort(a, lo0, lo); quickSort(a, hi, hi0); } } |
|