七种常用排序算法的实现和优化（Java语言实现）
本来想最近出一个全网最好的MySQL基础和高级总结 无奈昨天学校说我天天搞java不能毕业 最近可能不能学啥东西了
毕设是虚拟现实那块的 今天查论文也有用到mysql交互数据库 应该还是可以学学..尽量过年的时候发出来吧
排序也不太会 瞎总结的 像我这种新手可以学学
总体比较
排序接口
public interface Sort {
void sort(int[] arr);
void betterSort(int[] arr);
}
测试类
public int[] createArray(){
//定义数组长度
int[] arr=new int[10];
//随机赋值
Random random = new Random();
int max=100;
for(int i=0;i<arr.length;i++)
arr[i]=random.nextInt(max);
return arr;
}
//测试
public void testSort(String className) throws Exception {
int[] arr =createArray();
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
arr=createArray();
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
//排序10000000次比较两种排序算法的性能
long t1 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{50, 31, 93, 68, 37, 70, 15, 10, 21, 39};
sortObject.sort(arr);
}
long t2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
long t3 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{50, 31, 93, 68, 37, 70, 15, 10, 21, 39};
sortObject.betterSort(arr);
}
long t4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
} 稳定的排序
1 插入排序——直接插入排序
直接插入排序
- 原理：
假设前n-1个数是已经排好序的，将第n个数插入前面已经排好序的数列中，重复此过程直到插入完所有数。 - 时间复杂度 O(n²)
- 适用场景
n较小时以及元素基本有序时，可用来做其他排序的优化
//直接插入排序
public void sort(int[] arr){
//从第二个数开始插入
for(int index=1;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
int i;
for (i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
} 优化的直接插入排序：折半插入
- 原理：
直接插入并没有利用到要插入的数列已经有序的特点，可以通过二分查找找到要插入的位置i，将i+1到目前遍历到的索引index的之间的元素全部后移后插入。 - 时间复杂度 O(nlogn)
//优化的插入排序：折半插入
public void betterSort(int[] arr){
//从第二个数开始插入
for(int index=1;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置
int insertIndex = -1;
int start=0;
int end=index-1;
while (start<=end){
//中间索引
int mid=start+(end-start)/2;
//如果比temp小，从中间往后面部分找
if(arr[mid]<temp)
start=mid+1;
//如果比temp大，从中间往前面部分找
else if(arr[mid]>temp)
end=mid-1;
else
//出现相同元素时保证排序稳定性
insertIndex= mid+1;
break;
}
if(insertIndex==-1)
insertIndex=start;
//将插入位置开始直到目前有序数列长度的数全部后移一个腾出位置
for(int i=index;i>insertIndex;i--)
arr[i]=arr[i-1];
arr[insertIndex]=temp;
}
} 测试及性能比较
结果：可以看到优化后的插入排序性能更好
sort.InsertSort
排序前
[11, 43, 90, 65, 79, 36, 47, 37, 67, 77]
排序后
[11, 36, 37, 43, 47, 65, 67, 77, 79, 90]
排序前
[32, 1, 5, 60, 20, 67, 94, 22, 51, 21]
优化排序后
[1, 5, 20, 21, 22, 32, 51, 60, 67, 94]
优化前的排序1000万次花费时间：405ms
优化后的排序1000万次花费时间：355ms
2 交换排序——冒泡排序
冒泡排序
- 原理：
比较相邻的元素，如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
针对所有的元素重复以上的步骤，除了最后一个，直到没有任何一对数字需要比较。 - 时间复杂度 O(n²)
- 适用场景
元素基本有序时
public void sort(int[] arr) {
//对于n个元素的数组需要执行n-1次
for(int i=0;i<arr.length-1;i++){
//由于最后一个就是最大元素，所以不需要比较到最后一个
for(int index=0;index<arr.length-1-i;index++){
//如果比后面的元素大则交换
if(arr[index]>arr[index+1]){
int temp=arr[index];
arr[index]=arr[index+1];
arr[index+1]=temp;
}
}
}
} 优化后的冒泡排序
- 原理：
例如结束排序前元素序列为1，2，3，4，5，6，7，8，此时数列已经有序，但仍会进行不必要的比较，因此可以设置一个标志位falg，记录是否有元素交换，如果没有直接结束比较。
例如要对1，4，7，3，8，9，10，11这种前一半无序后一半有序的数列进行排序，为了减少不必要的比较，可以再加上一个临时变量记录最后一次元素交换的位置，作为下次比较的最大边界。 - 时间复杂度 O(n²)
public void betterSort(int[] arr) {
//记录数列是否有序
boolean flag=true;
//记录最后一次交换的数组下标
int lastIndex =-1;
//记录数组无序边界,初始为末尾
int bound=arr.length-1;
//对于n个元素的数组需要执行n-1次
for(int i=0;i<arr.length-1;i++){
for(int index=0;index<bound;index++){
//如果比后面的元素大则交换
if(arr[index]>arr[index+1]){
int temp=arr[index];
arr[index]=arr[index+1];
arr[index+1]=temp;
lastIndex=index;
flag=false;//有元素交换，说明数列无序
}
}
//更新边界值
bound=lastIndex;
//如果数列已有序，结束排序
if(flag)
break;;
}
} 测试及性能比较
结果：
sort.BubbleSort
排序前
[12, 59, 38, 95, 31, 88, 48, 12, 4, 51]
排序后
[4, 12, 12, 31, 38, 48, 51, 59, 88, 95]
排序前
[57, 85, 32, 43, 65, 58, 65, 67, 97, 79]
优化排序后
[32, 43, 57, 58, 65, 65, 67, 79, 85, 97]
优化前的排序1000万次花费时间：492ms
优化后的排序1000万次花费时间：462ms
3 归并排序
Arrays.sort是利用归并排序实现的
归并排序
原理
将数组分成两半，对每部分递归应用归并排序，在两部分都排好序后，对其进行合并。时间复杂度 O(nlogn)
适用场景
数据量大，并且对稳定性有要求的情况//辅助数组 长度和原数组相同 private int[] help; @Override public void sort(int[] arr) { help=new int[arr.length]; sort(arr,0,arr.length-1); } //排序 private void sort(int[] arr, int start, int end){ if(start==end) return; //防止溢出 int mid=start+(end-start)/2; //对前一半排序 sort(arr,start,mid); //对后一半排序 sort(arr,mid+1,end); //合并 merge(arr,start,mid,end); } // private void merge(int[] arr, int start, int mid, int end){ //将待排序序列arr[low...high]拷贝到辅助数组的相同位置 for(int i=start;i<=end;i++){ help[i]=arr[i]; } int p=start;//用于遍历前半部分数列的索引 int q=mid+1;//用于遍历后半部分数列的索引 int index=start;//遍历arr数组的索引 while(p<=mid&&q<=end){ //用较小的那一个更新数组 if(help[p]<help[q]) arr[index++]=help[p++]; else arr[index++]=help[q++]; } //如果还有剩余的则依次全部存入，以下两个while只会执行一个 while(p<=mid) arr[index++]=help[p++]; while(q<=end) arr[index++]=help[q++]; }
优化的归并排序
- 原理
由于排序后的左右部分已有序，所以如果下标为mid的元素小于下标为mid+1的元素就不再需要合并。
同时，当元素个数足够少的时候，我们可以使用直接插入排序。 - 时间复杂度 O(nlogn)
public void betterSort(int[] arr) {
help=new int[arr.length];
betterSort(arr,0,arr.length-1);
}
//优化排序
private void betterSort(int[] arr,int start, int end) {
//数列小于5时用插入排序优化
if(end-start<5){
InsSort(arr);
return;
}
//防止溢出
int mid=start+(end-start)/2;
//对前一半排序
betterSort(arr,start,mid);
//对后一半排序
betterSort(arr,mid+1,end);
//减少不必要的归并，由于前后均有序，若mid<mid+1,不必合并
if(arr[mid]>arr[mid+1])
merge(arr,start,mid,end);
}
public void InsSort(int[] arr){
//从第二个数开始插入
for(int index=1;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
int i;
for (i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
} 测试及性能比较
结果：
sort.MergeSort
排序前
[78, 69, 13, 93, 47, 91, 30, 59, 33, 59]
排序后
[13, 30, 33, 47, 59, 59, 69, 78, 91, 93]
排序前
[85, 75, 57, 32, 79, 17, 63, 58, 77, 55]
优化排序后
[17, 32, 55, 57, 58, 63, 75, 77, 79, 85]
优化前的排序1000万次花费时间：1779ms
优化后的排序1000万次花费时间：628ms
不稳定的排序
1 插入排序——希尔排序
希尔排序
- 原理
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。 - 时间复杂度 O(n^（1.3—2）)
- 适用场景
希尔排序是对直接插入排序的一种优化，可以用于大型的数组，希尔排序比插入排序和选择排序要快的多，并且数组越大，优势越大。//希尔排序 public void sort(int[] arr) { //初始增量为数组长度的1/2 for(int gap=arr.length/2;gap>0;gap/=2){ //循环直到增量gap为1时结束 for(int index=gap;index<arr.length;index++){ //保存目前的数 int temp=arr[index]; //寻找要插入的位置,从当前数的前gap个开始，直到数列开头 int i; for(i=index-gap;i>=0&&temp<arr[i];i-=gap){ //每当目前遍历到的数比temp大，就让它往后挪gap个，腾出位置 arr[i+gap]=arr[i]; } arr[i+gap]=temp; } } }由于希尔排序也是对直接插入排序的优化，所以两者的代码十分相似，和下面的直接插入排序比较，可以发现只是将间隔从1设置为了gap变量，并增加了一个控制gap变量的循环结构。
//直接插入排序
public void sort(int[] arr){
//从第二个数开始插入
for(int index=1;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
int i;
for (i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
} 优化的希尔排序
- 原理：
使用以下的序列，使性能提高 20%-40% 。1、5、19、41、109、209、505、929、2161、3905、8929、16001、36289、64769、146305、260609（这是通过 9×4k-9×2k+1(k=1,2,3,4,5…) 和 4k-3×2k+1(k=2,3,4,5,6…) 综合得到的）
public void betterSort(int[] arr) {
int length = arr.length;
int gap = 1;
while (gap < length / 19) {
gap = 19 * gap + 1; // 、5、19、41、109、209、505、929、2161、3905、8929、16001、36289、64769、146305、260609
}
while (gap>=1){
//循环直到增量gap为1时结束
for(int index=gap;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置,从当前数的前gap个开始，直到数列开头
int i;
for(i=index-gap;i>=0&&temp<arr[i];i-=gap){
//每当目前遍历到的数比temp大，就让它往后挪gap个，腾出位置
arr[i+gap]=arr[i];
}
arr[i+gap]=temp;
}
gap/=3;
}
} 测试及性能比较
为了测试此处增加测试数据长度，其余测试时使用最开头的长度为10的数组。
@Test
public void test() throws Exception {
testSort("sort.ShellSort");
}
//测试
public void testSort(String className) throws Exception {
int[] arr =createArray();
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
arr=createArray();
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
//排序10000000次比较两种排序算法的性能
long t1 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{50, 31, 93, 68, 37, 70, 15, 10, 21, 39,72,4,9,2,1,5,54,70,35,65,23,65,34,67,23,54,34,25,76,52,23,26,43
,4,55,2,42,65,4,24,56,74,35,745,35,36,75,73,56,45,24,75,45,7,87,24,26};
sortObject.sort(arr);
}
long t2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
long t3 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{50, 31, 93, 68, 37, 70, 15, 10, 21, 39,72,4,9,2,1,5,54,70,35,65,23,65,34,67,23,54,34,25,76,52,23,26,43
,4,55,2,42,65,4,24,56,74,35,745,35,36,75,73,56,45,24,75,45,7,87,24,26};
sortObject.betterSort(arr);
}
long t4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
} 结果：
sort.ShellSort
排序前
[39, 31, 24, 58, 63, 83, 49, 68, 80, 55]
排序后
[24, 31, 39, 49, 55, 58, 63, 68, 80, 83]
排序前
[9, 41, 47, 70, 81, 24, 53, 43, 72, 57]
优化排序后
[9, 24, 41, 43, 47, 53, 57, 70, 72, 81]
优化前的排序1000万次花费时间：3815ms
优化后的排序1000万次花费时间：2997ms
2 选择排序——直接选择排序
直接选择排序
- 原理：
首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
重复直到所有元素均排序完毕。 - 时间复杂度 O(n²)
- 适用场景
数据量不大，并且对稳定性没有要求的情况
public void sort(int[] arr) {
//存储最小元素下标
int minIndex;
for(int index=0;index<arr.length-1;index++){
minIndex=index;
//寻找最小元素,用其下标更新minIndex
for(int i=index+1;i<arr.length;i++){
if(arr[i]<arr[minIndex])
minIndex=i;
}
//如果最小元素不是当前元素，交换两者位置
if(index!=minIndex){
int temp=arr[minIndex];
arr[minIndex]=arr[index];
arr[index]=temp;
}
}
} 优化后的选择排序
- 原理：
同时在未排序数列中找到最小元素和最大元素，分别存放在数列头部和尾部。
重复直到所有元素均排序完毕。 - 时间复杂度 O(n²)
public void betterSort(int[] arr) {
//存储最小元素下标
int minIndex;
//存储最大元素下标
int maxIndex;
int start;
int end=arr.length-1;
for(start=0;start<end;start++,end--){
minIndex=start;
maxIndex=end;
//寻找最小元素,用其下标更新minIndex
//寻找最大元素,用其下标更新maxIndex
for(int i=start;i<=end;i++){
if(arr[i]<arr[minIndex])
minIndex=i;
if(arr[i]>arr[maxIndex])
maxIndex=i;
}
//如果最小元素不是当前起始元素，交换两者位置
if(start!=minIndex){
int temp=arr[minIndex];
arr[minIndex]=arr[start];
arr[start]=temp;
}
//如果最大元素不是当前末尾元素，交换两者位置
if(end!=maxIndex){
int temp=arr[maxIndex];
arr[maxIndex]=arr[end];
arr[end]=temp;
}
}
} 测试及性能比较
@Test
public void test() throws Exception {
testSort("sort.SelectSort");
} 结果：由于同时找到了最小和最大元素，几乎节约一半时间
sort.SelectSort
排序前
[93, 93, 48, 71, 94, 15, 74, 56, 45, 5]
排序后
[5, 15, 45, 48, 56, 71, 74, 93, 93, 94]
排序前
[66, 26, 59, 5, 6, 78, 9, 93, 2, 2]
优化排序后
[2, 2, 5, 6, 9, 26, 59, 66, 78, 93]
优化前的排序1000万次花费时间：934ms
优化后的排序1000万次花费时间：640ms
3 选择排序——堆排序
堆排序
- 原理
堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法。
最大堆要求节点的元素都要不小于其孩子，最小堆要求节点元素都不大于其左右孩子。
那么处于最大堆的根节点的元素一定是这个堆中的最大值。 - 时间复杂度 O(nlogn)
- 适用场景 数据较多时
- 给堆添加结点的思路
将最后一个结点作为当前结点
while(当前结点＞它的父结点){
将当前结点和它的父结点交换
现在当前结点往上面进了一个层次
} - 给堆移除结点的思路
移除根结点
将最后一个结点作为根结点
将根结点作为当前结点
while(当前结点具有子结点且小于它的子结点){
将当前结点和较大的子结点交换
现在当前结点往下面进了一个层次
}
用集合实现
private ArrayList<Integer> list=new ArrayList<>();
//建堆
private void add(int num){
list.add(num);
//获取当前索引
int curIndex=list.size()-1;
while (curIndex>0){
//获取父索引
int parIndex=(curIndex-1)/2;//例如二叉树0，1，2 1和2的父索引都是0
//如果当前索引的数值比父索引的数值大则交换，否则由于按序插入可直接结束
if(list.get(parIndex)<list.get(curIndex)){
int temp=list.get(parIndex);
list.set(parIndex,list.get(curIndex));
list.set(curIndex,temp);
}else break;
curIndex=parIndex;//如果交换，让当前索引=父索引，继续判断
}
}
//移除堆中最大元素
private int remove(){
//获取当前list中最大元素，由于是大根堆，所以是第一个
int rem=list.get(0);
//重建大根堆
list.set(0,list.get(list.size()-1));//让最后一个结点取代根结点
list.remove(list.size()-1);//移除最后一个结点
int curIndex=0;//让根结点成为当前结点
while(curIndex<list.size()){
int leftIndex=curIndex*2+1;//左孩子结点索引
int rightIndex=curIndex*2+2;//右孩子结点索引
if(leftIndex>=list.size()) break;//到达末尾
//寻找最大孩子结点索引
int maxIndex=leftIndex;
if(rightIndex<list.size()){//如果右孩子结点存在
if(list.get(maxIndex)<list.get(rightIndex))
maxIndex=rightIndex;
}
//如果最大孩子结点值大于当前结点，则交换
int temp=list.get(curIndex);
if(list.get(curIndex)<list.get(maxIndex)){
list.set(curIndex,list.get(maxIndex));
list.set(maxIndex,temp);
}
else break;
curIndex=maxIndex;
}
//返回最大值
return rem;
}
@Override
public void sort(int[] arr) {
//依次添加元素，即建堆
for (int value : arr) add(value);
//依次移除最大元素并赋值排序
for(int i=arr.length-1;i>=0;i--)
arr[i]=remove();
} 优化的堆排序
- 原理
整体思路不变，用数组取代集合
public void betterSort(int[] arr) {
int[] nums=new int[arr.length];
int i=0;
int size=arr.length;
for (int value : arr)
badd(nums,i++,value);
for(int index=arr.length-1;index>=0;index--)
arr[index]=bremove(nums,size--);
}
private void badd(int[] nums,int i,int num){
nums[i]=num;
int curIndex=i;
while (curIndex>0){
int parIndex=(curIndex-1)/2;
if(nums[parIndex]<nums[curIndex]){
int temp=nums[curIndex];
nums[curIndex]=nums[parIndex];
nums[parIndex]=temp;
}else break;
curIndex=parIndex;
}
}
private int bremove(int[] nums,int size){
int rem=nums[0];
nums[0]=nums[size-1];
int curIndex=0;
while(true){
int leftIndex=curIndex*2+1;
int rightIndex=curIndex*2+2;
if(leftIndex>=size) break;
int maxIndex=leftIndex;
if(rightIndex<size){
if(nums[maxIndex]<nums[rightIndex])
maxIndex=rightIndex;
}
int temp=nums[curIndex];
if(nums[curIndex]<nums[maxIndex]){
nums[curIndex]=nums[maxIndex];
nums[maxIndex]=temp;
}
else{
break;}
curIndex=maxIndex;
}
//返回最大值
return rem;
} 测试及性能比较
@Test
public void test() throws Exception {
testSort("sort.HeapSort");
}
//测试
public void testSort(String className) throws Exception {
int[] arr=new int[]{3,5,1,19,11,22,88};
Class<Sort> aClass = (Class<Sort>) Class.forName(className);
Sort sortObject = aClass.newInstance();
System.out.println(className);
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("排序后");
sortObject.sort(arr);
System.out.println(Arrays.toString(arr));
arr=new int[]{3,5,1,19,11,22,88};
System.out.println("排序前");
System.out.println(Arrays.toString(arr));
System.out.println("优化排序后");
sortObject.betterSort(arr);
System.out.println(Arrays.toString(arr));
//排序10000000次比较两种排序算法的性能
long t1 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{3,5,1,19,11,22,88};
sortObject.sort(arr);
}
long t2 = System.currentTimeMillis();
System.out.println("优化前的排序1000万次花费时间："+(t2-t1)+"ms");
long t3 = System.currentTimeMillis();
for(int i=0;i<10000000;i++){
arr=new int[]{3,5,1,19,11,22,88};
sortObject.betterSort(arr);
}
long t4 = System.currentTimeMillis();
System.out.println("优化后的排序1000万次花费时间："+(t4-t3)+"ms");
} 结果：
sort.HeapSort
排序前
[3, 5, 1, 19, 11, 22, 88]
排序后
[1, 3, 5, 11, 19, 22, 88]
排序前
[3, 5, 1, 19, 11, 22, 88]
优化排序后
[1, 3, 5, 11, 19, 22, 88]
优化前的排序1000万次花费时间：1449ms
优化后的排序1000万次花费时间：486ms
4 交换排序——快速排序
快速排序
- 原理：
对冒泡排序的优化。
该算法在数组中选择一个基准（pivot）元素，将数组分为两部分，使得第一部分的元素都小于等于基准元素，第二部分的所有元素都大于基准元素，对第一部分和第二部分分别递归应用快速排序算法。 - 时间复杂度 O(nlogn)
- 适用场景
数据量大的情况
public void sort(int[] arr) {
quickSort(arr,0, arr.length-1);
}
public void quickSort(int[] arr,int start,int end){
//递归条件
if(start<end){
//排序并获得基准元素的下标
int pivotIndex=getPivotIndex(arr,start,end);
//分别对基准元素的前后部分排序
quickSort(arr,start,pivotIndex-1);
quickSort(arr,pivotIndex+1,end);
}
}
private int getPivotIndex(int[] arr, int start, int end) {
//默认选择第一个作为基准
int pivot=arr[start];
int i=start;
int j=end;
while(i<j){//循环条件
//从左起找到第一个大于pivot的元素
while (i<=j&&arr[i]<=pivot)
i++;
//从右起找到第一个小于等于pivot的元素
while (i<=j&&arr[j]>pivot)
j--;
//如果左边元素大于右边则交换
if(i<j){
swap(arr,i,j);
}
}
swap(arr,start,j);
return j;
}
public static void swap(int[] arr, int x, int y){
int temp;
temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
} 优化的快速排序
- 原理
当规模足够小时，我们可以采用直接插入排序
public void betterSort(int[] arr) {
bquickSort(arr,0, arr.length-1);
}
public void bquickSort(int[] arr,int start,int end){
//递归条件
if(end-start<5){
InsSort(arr);
}
//排序并获得基准元素的下标
int pivotIndex=getPivotIndex(arr,start,end);
//分别对基准元素的前后部分排序
quickSort(arr,start,pivotIndex-1);
quickSort(arr,pivotIndex+1,end);
}
public void InsSort(int[] arr){
//从第二个数开始插入
for(int index=1;index<arr.length;index++){
//保存目前的数
int temp=arr[index];
//寻找要插入的位置,从当前数的前一个开始，直到数列开头
int i;
for (i=index-1;i>=0&&arr[i]>temp;i--){
//每当目前遍历到的数比temp大，就让它往后挪一个，腾出位置
arr[i+1]=arr[i];
}
arr[i+1]=temp;
}
} 测试及性能比较
#Java工程师##笔记#sort.QuickSort
排序前
[0, 89, 27, 27, 66, 83, 21, 53, 74, 52]
排序后
[0, 21, 27, 27, 52, 53, 66, 74, 83, 89]
排序前
[81, 0, 83, 5, 86, 39, 7, 61, 43, 88]
优化排序后
[0, 5, 7, 39, 43, 61, 81, 83, 86, 88]
优化前的排序1000万次花费时间：621ms
优化后的排序1000万次花费时间：495ms
投递拼多多等公司10个岗位