一，基本信息
描述
被列为20世纪十大算法之一
c++ STL, java SDK 等开放工具包的源代码都有它的某种实现版本
思路： 通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比铃一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
案例
复杂度
-
时间复杂度
- 平均最好O(NlogN)
- 最坏 O(N2)
- 每次划分分为一个元素，和 其他元素 两个部分。
- 空间复杂度: O(logn)
代码
package com.datastructure.sort;
import java.util.Arrays;
/**
* QuickSort class
*/
public class QuickSort {
public void sort(long[] sqList, int low, int high){
//中间数下标
int middle;
if(low < high) {
//算出中间值下标
middle = partition(sqList,low,high);
sort(sqList,low,middle-1);
sort(sqList,middle+1,high);
}
}
public int partition(long[] sqList, int low, int high) {
long t, middleValue = sqList[low];
// 从数组两端交替向中间扫描
while (low < high) {
// 保证右边的大于等于中间值
while (low < high && sqList[high] >= middleValue )
high --;
swap(sqList,low,high);
// 保证左边的小于等于中间值
while (low < high && sqList[low] <= middleValue)
low ++;
swap(sqList,low,high);
}
return low;
}
public void swap(long[] sqList, int low, int high) {
long t = sqList[low];
sqList[low] = sqList[high];
sqList[high] = t;
}
public static void main(String[] args) {
long[] sqList = {50,10,90,30,70,40,80,60,20};
QuickSort quickSort = new QuickSort();
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
sqList = new long[]{50, 10, 90, 30, 70, 40, 80, 60};
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
}
}
- 控制台输出
[10, 20, 30, 40, 50, 60, 70, 80, 90]
[10, 30, 40, 50, 60, 70, 80, 90]
优化
- 优化选取中间数
- 三数取中法
- partition方法 middleValue = 中间(sqList[low],sqList[high], sqList[low + (hight- low) /2] )
- 三数取中法
- 优化不需要的交换
- 根据数据规范改变算法
- 并行处理
- 优化递归操作
代码
// 优化选取中间数 优化不需要的交换 后
package com.datastructure.sort;
import java.util.Arrays;
/**
* QuickSort class
*/
public class QuickSort {
public void sort(long[] sqList, int low, int high){
//中间数下标
int middle;
if(low < high) {
//算出中间值下标
middle = partition(sqList,low,high);
sort(sqList,low,middle-1);
sort(sqList,middle+1,high);
}
}
public int partition(long[] sqList, int low, int high) {
long t;
int m = low + (high - low) / 2 ;
// 三个数 取中间值，把中间值放到sqList[low]
if(sqList[low] > sqList[high])
swap(sqList,low,high);
if(sqList[m] > sqList[high])
swap(sqList,m,high);
if(sqList[m] > sqList[low] )
swap(sqList,m,low);
long middleValue = sqList[low];
// 从数组两端交替向中间扫描
while (low < high) {
// 保证右边的大于等于中间值
while (low < high && sqList[high] >= middleValue )
high --;
sqList[low] = sqList[high];
// swap(sqList,low,high);
// 保证左边的小于等于中间值
while (low < high && sqList[low] <= middleValue)
low ++;
sqList[high] = sqList[low];
// swap(sqList,low,high);
}
sqList[low] = middleValue;
return low;
}
public void swap(long[] sqList, int low, int high) {
long t = sqList[low];
sqList[low] = sqList[high];
sqList[high] = t;
}
public static void main(String[] args) {
long[] sqList = {50,10,90,30,70,40,80,60,20};
QuickSort quickSort = new QuickSort();
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
sqList = new long[]{50, 10, 90, 30, 70, 40, 80, 60};
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
}
}
二、 稳定性。
- 稳定性定义
- 稳定排序算法会让原本有相等键值的纪录维持相对次序。
1. 用一个O(N) 内存来 实现快排的稳定性
- 寻找中间数的下标 只能是第一个。
- 3 2 3 3 4。如果选 2 下标的3 ，还是会打乱顺序。
public class QuickPacifySort {
public void sort(long[] sqList, int low, int high){
//中间数下标
int middle;
if(low < high) {
//算出中间值下标
middle = partition(sqList,low,high);
sort(sqList,low,middle-1);
sort(sqList,middle+1,high);
}
}
public int partition(long[] sqList, int low, int high) {
if( low >= high) {
return low;
}
int offset = low;
long middleValue = sqList[low];
List<Long> leftList = new ArrayList<>();
List<Long> rightList = new ArrayList<>();
for(int i = low; i <= high; i ++) {
if(sqList[i] < middleValue) {
leftList.add(sqList[i]);
} else {
rightList.add(sqList[i]);
}
}
int start = 0;
for(; start < leftList.size(); start ++) {
sqList[low + start] = leftList.get(start);
}
start = low + start;
for(int i = 0; i < rightList.size(); i ++) {
sqList[start ++] = rightList.get(i);
}
return low;
}
public void swap(long[] sqList, int low, int high) {
long t = sqList[low];
sqList[low] = sqList[high];
sqList[high] = t;
}
public static void main(String[] args) {
long[] sqList = {50,10,90,30,70,40,80,60,20};
QuickPacifySort quickSort = new QuickPacifySort();
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
sqList = new long[]{50, 10, 90, 30, 70, 40, 80, 60};
quickSort.sort(sqList,0,sqList.length-1);
System.out.println(Arrays.toString(sqList));
}
}
