排序-快速排序
2020-03-20 本文已影响0人
格林哈
描述
-
被列为20世纪十大算法之一
-
c++ STL, java SDK 等开放工具包的源代码都有它的某种实现版本
-
思路: 通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
案例
复杂度
-
时间复杂度:O(nlogn)
- log 描述以 2为底对数
- 空间复杂度: 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));
}
}