Java实现快速排序
直接插入排序
希尔排序
简单选择排序
堆排序
冒泡排序
快速排序
归并排序
根据算法的简单性进行分类:
简单算法:冒泡、简单选择、直接插入
改进算法:希尔、堆、归并、快速
排序算法的性能主要受三个方面影响:
时间性能
辅助空间
算法的复杂性
七种排序算法的各种指标对比如下图所示。
这七种排序算法,应该说没有一种是绝对占优的。冒泡排序逻辑最简单,这个相信大家都会,而堆排序我也写过一篇文章了专门介绍
本文介绍的快速排序算法,可以认为是最慢的冒泡排序的升级。
2、Java实现快速排序的代码
快速排序算法的思想以及代码的注释都在下面,大家可以直接将代码copy到本地方便学习。
package com.bobo.sort;
/**
* 快速排序思想:
* 1、从数组中选取一个元素作为基准值(一般是第一个),将待排序的数组分成左右两部分,左边的部分小于基准值,右边的部分大于基准值;
* 2、使用左右两个指针向中间移动(可以约定右指针先移动),左边的指针移到到比基准值大的下标时停下,右边的指针移动到比基准小的下标时停下,
* 然后双方交换数组元素,继续向左、向右移动;
* 3、当左右指针重合时,有两种情况:
* 基准值大于重合处元素:将基准值与重合处元素交换,一轮结束,以重合处下标为分界线,分成左右两部分,递归排序;
* 基准值小于等于重合处元素:将基准值与重合处上一个元素交换,一轮结束,以重合处上一个下标为分界线,分成左右两部分,递归排序;
*/
public class QuickSort {
/**
* 用于验证待排序序列,避免出现数组下标越界异常
*/
public static boolean valid(int[] array,int base,int low,int high){
// 避免出现数组下标越界异常
if(base>low || base>high || low>high){
return false;
}
//只有一个元素的情况:base=low=high
if(base == low && low == high){
return false;
}
//只有两个元素的情况:base<low=high
if(base < low && low == high){
//只有两个元素时,直接比较交换,无需走快排
if(array[base] > array[high]){
int temp = array[base];
array[base] = array[high];
array[high] = temp;
}
return false;
}
//三个及三个以上元素的情况:base<low<high
return true;
}
/**
* 快速排序
* @param array 待排序数组
* @param base 基准值下标
* @param low low下标
* @param high high下标
*/
public static void qSort(int[] array,int base,int low,int high){
if(!valid(array,base,low,high)){
return;
}
int i=low,j=high;
for (;;){
// 右指针移动
while (array[j] >= array[base] && j>i){
j--;
}
// 左指针移动
while (array[i] <= array[base] && j>i){
i++;
}
// 左右指针重合时,走if
if(j==i){
if(array[i] < array[base]){
// 基准值大于重合处元素时,走if;将基准值与重合处元素交换
int temp = array[base];
array[base] = array[i];
array[i] = temp;
// 分成左右两半,递归排序
qSort(array,base,low,i-1);
qSort(array,i+1,i+2,high);
}else if(array[i] >= array[base]){
// 基准值小于等于重合处元素,走else;将基准值与重合处上一个元素交换
int temp = array[base];
array[base] = array[i-1];
array[i-1] = temp;
// 分成左右两半,递归排序
qSort(array,base,low,i-2);
qSort(array,i,i+1,high);
}
// 一轮结束,return
return;
}else{
// 左右指针没重合时,走else;交换左右指针对应的元素
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
public static void main(String[] args) {
int[] array = new int[]{-419,-419,452,451,267,-205,-114,82,-323,0};
qSort(array,0,1,array.length-1);
for (int i : array) {
System.out.println(i);
}
}
}
为了确保代码的正确性,我专门找了力扣的一道题做验证,详情请见力扣的912题-排序数组,https://leetcode-cn.com/problems/sort-an-array/。
学习快速排序然后写代码花了一个小时,从第一次运行到通过这期间改bug也花了一个小时,幸好最终是ok的。