快速排序算法的三种方式及其优化java实现
快速排序算法的三种方式及其优化java实现
1、快速排序算法的简绍
快速排序算法(QuickSort)又称为划分交换排序，快速排序是对冒泡排序的一种改进方法，在冒泡排序中，记录关键字的比较和交换是在相邻记录之间进行的，记录每次交换只能上移或下移一个相邻位置，因而总的比较和移动次数较多；在快速排序中，记录关键字的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面的单元，关键字较小的记录一次就能交换到前面的单元(升序)，记录每次移动的距离较远，因而总的比较和移动次数较少，速度很快，所以被称为快速排序。
2、快速排序的基本思想
首先当前无序区data[low…high]中任取一个记录作为排序比较的基准（不妨设为x,其位置为i），用次基准将当前无序区划分为两个较小的无序区：data[low…i-1]和data[i+1…high]，并使左边的无序区中所有的记录的关键字均小于等于基准的关键字，右边的无序区中所有的记录的关键字均大于等于基准的关键字，即data[low…i-1]中的关键字<=x.key<=data[i+1…high]中的关键字，这个过程称为一趟快速排序（或一次划分）。当data[low…i-1]和data[i+1…high]均非空时，分别对它们进行上诉划分过程，直到所有无序区中的记录均已排序好为止。
3、快速排序左右指针法图解
1、选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。 设置两个变量left = 0;right = N - 1。
2、 从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
3、重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。
4、快速排序左右指针法核心代码
public class Quick_Sort4 {
public static void quickSort(int[] arrays, int low, int hi) {
if (low < hi) {
// 求每次分治的分割线
int divideIndex = getDivideIndex(arrays, low, hi);
// 再递归分别对分割的俩个子数组进行递归排序
quickSort(arrays, low, divideIndex - 1);
quickSort(arrays, divideIndex + 1, hi);
}
}
public static int getDivideIndex(int[] arrays, int low, int hi) {
// 设定arrays[low]为基准值,从右到左移动hi,找到大于第一个大于基准值的数字。
// 从左向右移动low指针,找到第一个小于基准值的数,交换low和high位置上的值
// 直到low=high的时候，将基准值填入arrays[low]
int baseValue = arrays[low];
int oldLow = low;
while (low < hi) {
while (low < hi && arrays[hi] >= baseValue) {
hi--;
}
while (low < hi && arrays[low] <= baseValue) {
low++;
}
if (low < hi) {
swap(arrays, low, hi);
}
}
if (low == hi) {
arrays[oldLow] = arrays[low];
arrays[low] = baseValue;
}
return low;
}
public static void swap(int[] arrays, int low, int high) {
int temp = 0;
temp = arrays[low];
arrays[low] = arrays[high];
arrays[high] = temp;
}
public static void main(String[] args) {
// 显示排序前的序列
int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
System.out.println("快速排序之左右指针排序前:");
for (int data : arrays) {
System.out.print(data + " ");
}
System.out.println();
getDivideIndex(arrays, 0, arrays.length - 1);
System.out.println("第一趟排序结果:");
for (int data : arrays) {
System.out.print(data + " ");
}
System.out.println();
quickSort(arrays, 0, arrays.length - 1);
System.out.println("快速排序之左右指针排序后:");
for (int data : arrays) {
System.out.print(data + " ");
}
}
}
运行结果：
5、快速排序挖坑法图解
1、选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序 列最后一个数为枢轴，也是初始的坑位。
2、设置两个变量left = 0;right = N - 1;
3、从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。
4、right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成了array[right]。
5、重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。
6、当left >= right时，将key放入最后一个坑，就完成了一次排序。
注意：left走的时候right是不动的，反之亦然。因为left先走，所有最后一个坑肯定在array[right]。
6、快速排序挖坑法核心代码
运行结果：
7、快速排序前后指针法图解
定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。
当array[cur] < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。
当array[cur]再次 < key时，交换array[cur]和array[pre]。
通俗一点就是，在没找到大于key值前，pre永远紧跟cur，遇到大的两者之间机会拉开差距，中间差的肯定是连续的大于key的值，当再次遇到小于key的值时，交换两个下标对应的值就好了。
8、快速排序前后指针法核心代码
public class Quick_Sort3 {
public static void main(String[] args) {
int[] arrays = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
System.out.println("快速排序之左右指针排序前:");
for (int data : arrays) {
System.out.print(data + " ");
}
System.out.println();
partion(arrays, 0, arrays.length - 1);
System.out.println("第一趟排序结果:");
for (int data : arrays) {
System.out.print(data + " ");
}
System.out.println();
quickSort(arrays, 0, arrays.length - 1);
System.out.println("快速排序之左右指针排序后:");
for (int data : arrays) {
System.out.print(data + " ");
}
}
static int partion(int arr[], int left, int right) {
int pCur = left;
int prev = pCur - 1;
int key = arr[right];
while (pCur <= right) {
if (arr[pCur] <= key && (++prev) != pCur)
swap(arr, prev, pCur);
pCur++;
}
return prev;
}
static void quickSort(int arr[], int left, int right) {
if (left < right) {
int mid = partion(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
}
public static void swap(int[] arrays, int low, int high) {
int temp = 0;
temp = arrays[low];
arrays[low] = arrays[high];
arrays[high] = temp;
}
}
运行结果：
9、快速排序基准点优化及其核心代码
对于基准点的优化一般有三种：固定切分，随机切分和三数取中法。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N^2)。对于三数取中选择基准点是最理想的一种。
下面给出三个数取中间数的算法实现：
public class Quick_Sort {
public static void quickSort(int[] a, int low, int high) {
if (low >= high) {
return;
}
// 进行第一轮排序获取分割点
int index = partSort(a, low, high);
// 排序前半部分
quickSort(a, low, index - 1);
// 排序后半部分
quickSort(a, index + 1, high);
}
public static int partSort(int[] a, int low, int high) {
// 调用三数取中
int mid = Quick_Sort.getMid(a, low, high);
swap(mid, a[high]);
int key = a[high];
while (low < high) {
// 从前半部分向后扫描
while (low < high && a[low] <= key) {
++low;
}
a[high] = a[low];
// 从后半部分向前扫描
while (low < high && a[high] >= key) {
--high;
}
a[low] = a[high];
}
// 最后把基准点存入
a[high] = key;
return low;
}
public static int getMid(int[] a, int low, int high) {
int mid = low + (high - low) / 2;
// 下面两步保证了a[high]是最大的
if (a[mid] > a[high]) {
swap(a[mid], a[high]);
}
if (a[low] > a[high]) {
swap(a[low], a[high]);
}
// 将a[low]和a[mid]比较，让较小的在啊[low]的位置
if (a[mid] > a[low]) {
swap(a[mid], a[low]);
}
int key = a[low];
return key;
}
public static void swap(int a, int b) {
int temp = a;
a = b;
b = temp;
}
public static void main(String[] args) {
// 显示排序前的序列
int[] array = { 36, 25, 48, 12, 65, 25, 43, 58, 76, 32 };
System.out.print("排序前:");
for (int data : array) {
System.out.print(data + " ");
}
System.out.println();
// 显示排序后的序列
Quick_Sort.quickSort(array, 0, 9);
System.out.print("排序后：");
for (int data : array) {
System.out.print(data + " ");
}
}
}
运行结果：
10、快速排序算法的时间复杂度
10.1最优情况下
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组；
此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间；
下面来推算下，在最优的情况下快速排序时间复杂度的计算(用迭代法)：
T[n] = 2T[n/2] + n ----------------第一次递归
令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归
= 2^2 T[ n/ (2^2) ] + 2n
令：n = n/(2^2) = 2^2 { 2 T[n/ (2^3) ] + n/(2^2)} + 2n ----------------第三次递归
= 2^3 T[ n/ (2^3) ] + 3n
…
令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = n + nlogn ；其中n为元素个数
又因为当n >= 2时：nlogn >= n (也就是logn > 1)，所以取后面的 nlogn；
综上所述：快速排序最优的情况下时间复杂度为：O( nlogn )
10.2最差情况下
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;
综上所述：快速排序最差的情况下时间复杂度为：O( n^2 )
10.3平均时间复杂度
快速排序的平均时间复杂度是：O(nlogn)
11、快速排序的稳定性
因为在快速排序的时候，即使待排序元素可基数相等也需要移动待排序元素的位置使得有序，所以快速排序是不稳定的