转载请注明出处
作者：@ZJXin
说明：本文所写的排序,默认按从小到大排序。由于本人水平有限，如有不正确的地方欢迎留言指出，谢谢！
排序算法是面试中经常会被问到的问题，甚至会要求手写算法，本文对一些常用的排序算法做了总结。本文涉及的代码全部都运行验证过。(堆排序没有给出代码实现)
排序算法分类
1. 直接插入排序
算法思想
每次将无序区的第一个记录按关键字插入到有序区的合适位置。
算法实现步骤
- 取出无序区第一个元素，并将该值赋值给一个临时变量
- 在已经排序的元素序列中从后向前扫描
- 如果所取元素大于新元素，将该元素向后移动一个位置
- 重复步骤三，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置中
- 重复1~5
算法流程图
直接插入排序
Java代码实现
/**
* 直接插入排序算法
*
* @param nums 待排序数组
*/
public void insertSort(int []nums){
//数组长度
int length = nums.length;
//要插入的数
int insertNum;
for(int i=1;i<length;i++){//遍历数组
int j = i-1;//已排好序的元素序列的最大下标
insertNum = nums[i];
while(j>=0 && nums[j]>insertNum){
//首先判断j是否>=0,不然将可能产生数组溢出
//序列从后往前循环
//将大于insertNum的数往后挪一格
nums[j+1] = nums[j--];
}
//将需要插入的数放在插入的位置
nums[j+1] = insertNum;
}
}
算法分析
- 时间复杂度
- 最佳情况：O(n)
- 最坏情况：O(n^2)
- 平均时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定
- 改进：希尔排序(缩小增量排序)
2. 希尔排序（缩小增量排序）
算法思想
希尔排序是对直接插入排序的一种改进。希尔排序将整个待排序序列按增量dk划分为m个子序列，不断缩小增量dk，重复这一过程，直到dk减少到1，对整个序列进行一次直接插入排序，因此，希尔排序也被称为缩小增量排序。
希尔排序与直接插入排序的不同之处在于，直接插入排序每次对相邻记录进行比较，记录只移动一个位置，而希尔排序每次对相隔较远(即增量)的记录进行比较，使得记录移动时跨越多个记录，实现宏观上的调整。当增量为1时，此时序列已基本有序，可将前边的各趟的调整看做最后一趟的预处理。
算法实现步骤
- 选择一个增量序列t1、t2、t3...tk(其中tk=1)
- 按增量序列个数k，对待排序序列进行k趟排序
- 每趟排序，根据相应的增量dk，进行插入排序
算法流程图
希尔排序
Java代码实现
/**
* 希尔排序(缩小增量排序)
* 不稳定
*
* @param nums 待排序数组
*/
public void sheelSort(int []nums){
int dk = nums.length;
do{
//缩小增量
//此处缩小增量可以自己设置，一般缩小当前的一半
dk = dk/2;
sheelInsert(nums, dk);//进行一次希尔排序
}while(dk>0);//当增量为1时停止
}
/**
* 希尔排序一趟排序
* 如果把增量设置为1，则是简单的插入排序
*
* @param nums 待排序数组
* @param dk 增量
*/
public void sheelInsert(int []nums,int dk){
int length = nums.length;
int insertNum;//待插入的值
for(int i=dk;i<length;i++){
int j=i-dk;
insertNum = nums[i];
while(j>=0 && nums[j]>insertNum){
//同样的，应该先检测j是否比0小，否则可能产生数组溢出
//向后移动dk位
nums[j+dk] = nums[j];
j = j-dk;
}
nums[j+dk] = insertNum;//把待插入的 值放到正确的位置
}
}
算法分析
- 时间复杂度
- 最佳情况:O(n)
- 最坏情况:O(n^2)
- 平均情况:O(nlogn)
- 空间复杂度:O(1)
- 稳定性:不稳定
3. 简单选择排序
算法思想
每趟在未排序的序列中找到最小的元素，存放到未排序序列的起始位置。
算法实现步骤
- 首先在未排序序列中找到最小元素，存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
- 重复上述步骤，直到所有元素均排序完毕。
算法流程图
简单选择排序
Java代码实现
/**
* 简单选择排序
* 每一个循环后再交换，简单选择排序
*
* @param nums 待排序数组
*/
public void selsectSort(int []nums){
int length = nums.length;//数组长度，将这个值提出来，提高速度
for(int i=0; i<length; i++){//循环次数
int key = nums[i];
int position = i;
for(int j=i+1;j<length;j++){//选出最小的值和位置
if(key>nums[j]){
key = nums[j];
position = j;
}
}
//交换位置
nums[position] = nums[i];
nums[i] = key;
}
}
算法分析
- 时间复杂度
- 最坏、最佳、平均:O(n^2)
- 空间复杂度：O(1)
- 稳定性:不稳定
4. 堆排序
算法思想
堆排序是对简单排序的优化，利用大顶堆所有非叶子结点均不小于其左右孩子结点这一特性来排序。
算法实现步骤
- 将待排序列建成一个大顶堆
- 将顶堆结点与队尾结点交换位置，堆长度减1
- 调整剩余结点为堆
- 重复步骤2~3
算法流程图
堆排序
算法分析
- 时间复杂度
- 最坏、最好、平均：O(nlogn)
- 空间复杂度:O(1)
- 稳定性：不稳定
5. 冒泡排序
算法思想
冒泡排序每趟排序，对相邻两个元素进行比较，如果顺序错误则交换过来，每趟排序后，都将把未排序序列的最大值放在最后边。每趟排序，越小的元素会经由交换，慢慢地"浮"到数列顶端，这也是该算法名字的由来。
算法实现步骤
- 将序列中所有元素相邻两两比较，将最大的放在最后面。
- 将剩余序列中所有元素相邻两两比较，将最大的放在最后面。
- 重复第二步，直到只剩下一个数。
算法流程图
冒泡排序
Java代码实现
/**
* 冒泡排序
*
* @param nums 待排序数组
*/
public void bubbleSort(int []nums){
int length = nums.length;
int temp;
for(int i=0; i<length; i++){
for(int j=0; j<length-i-1; j++){
if(nums[j]>nums[j+1]){
//交换相邻两个数
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
算法分析
- 时间复杂度：
最佳、最坏、平均:O(n^2) - 空间复杂度：O(1)
- 稳定性：稳定
算法改进
- 改进方案一
设置一标志性变量pos，用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
/**
* 冒泡排序改进版本一
* 通过设置标志位来减少遍历次数
*
* @param nums
*/
public void betterBubbleSort1(int []nums){
int length = nums.length;
int i= length -1; //初始时,最后位置保持不变
while ( i> 0) {
int pos= 0; //每趟开始时,无记录交换
for (int j = 0; j< i; j++){
if (nums[j]> nums[j+1]) {
pos= j; //记录交换的位置
int tmp = nums[j];
nums[j]=nums[j+1];
nums[j+1]=tmp;
}
i= pos; //为下一趟排序作准备
}
}
}
- 改进方案二
若某一趟排序中未进行一次交换，则排序结束 。
/**
* 冒泡排序改进版本二
*
* @param nums 待排序数组
*/
public void betterBubbleSort2(int[] nums ) {
int len = nums .length;
boolean flag = true;
while (flag) {
flag = false;
for (int i = 0; i < len - 1; i++) {
if (nums [i] > nums [i + 1]) {
int temp = nums [i + 1];
nums [i + 1] = nums [i];
nums [i] = temp;
flag = true;
}
}
len--;
}
}
6. 快速排序
算法思想
分治法。通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后在分别对这两部分记录进行排序。
算法实现步骤
- 从数列中挑出一个元素，称为“基准”
- 重新排序数列，所有比基准小的元素放在基准前边，所有比基准大的放在基准后边，该基准最后处于数列中间位置。
- 递归地把小于基准值元素和大于基准值元素的子序列快速排序
算法流程图
快速排序
Java代码实现
/**
* 快速排序
* 不稳定
*
* @param nums 待排序数组
* @param left 开始位置
* @param right 结束位置
*/
public void quickSort(int []nums,int left,int right){
if(left<right){
int base = nums[left];//选定的基准
int low = left;
int high = right;
while(low<high){
while(low<high && nums[high]>base){
//先从后往前遍历,直到数值比基准小
high--;
}
//把数值比基准小的放到基准左边
nums[low] = nums[high];
while(low<high && nums[low]<base){
//从前往后遍历，直到数值比基准大
low++;
}
//把数值比基准大的放到基准右边
nums[high] = nums[low];
}
//把基准放到准确位置去
nums[low] = base;
//用同样的方法,递归调用基准左边的数组以及右边的数组
quickSort(nums, left, low-1);
quickSort(nums, low+1, right);
}
}
算法分析
- 时间复杂度
- 最佳情况：O(nlogn)
- 最坏情况：O(n^2)
- 平均复杂度:O(nlogn)
- 空间复杂度:O(nlogn)
- 稳定性:不稳定
7.归并排序
算法思想
分治法。归并排序将待排序列一分为二，并对每个子数组递归排序，然后再把这两个排好序的子数组合并为一个有序的数组。
算法实现步骤
- 把长度为n的输入序列分为两个长度为n/2的子序列
- 对这两个子序列分别采用归并排序
- 将两个排序好的子序列合并成一个最终的排序序列
算法流程图
归并排序
Java代码实现
/**
* 归并排序
* 稳定的排序算法
*
* @param nums 待排序数组
* @param low 待排序数组的起点
* @param high 待排序数组的终点
*/
public static void mergeSort(int []nums,int low,int high){
//算出分割点,2-路归并即数组的中点
int mid = (high+low)/2;
if(low<high){
//递归分割
mergeSort(nums, low, mid);
mergeSort(nums, mid+1, high);
//调用归并方法,将分割的进行归并
merge(nums, low, mid, high);
}
}
/**
* 一次2-路归并
* 可以想象成将两个链表，按照升序的方法组合成一条链表
*
* @param nums 待排序数组
* @param low 归并的最低位
* @param mid 归并的中间位置
* @param high 归并的最高位
*/
public static void merge(int []nums,int low,int mid,int high){
//新建数组，放置临时数据
int []temp = new int[high-low+1];
int i = low,j=mid+1;
int k=0;
//把较小的数先移到新数组中去
while(i<=mid && j<=high){
//遍历两路数组,直到一路结束为止
if(nums[i]<nums[j]){
temp[k++] = nums[i++];
}else{
temp[k++] = nums[j++];
}
}
//把左边那路剩余的数放入数组
while(i<=mid){
temp[k++] = nums[i++];
}
//把右边那路剩余的数放入数组
while(j<=high){
temp[k++] = nums[j++];
}
//把新数组的值覆盖nums数组
//新数组的长度有可能比nums数组短
for(int t=0;t<temp.length;t++){
nums[t+low] = temp[t];
}
}
算法分析
- 时间复杂度
- 最佳、最坏、平均:O(nlogn)
- 空间复杂度:O(n)
- 稳定定：稳定
- 优劣
- 优点：稳定性，性能不受输入数据的影响
- 缺点：需要线性的额外空间
8. 基数排序
算法思想
先将所有关键字统一为相同位数，位数较少的数前边补0.然后从最低位开始依次向高位进行排序，直到按最高位排序完成，关键字序列就成为有序序列。基数排序基于分别排序，分别收集，所以是稳定的。适用于很长的数的排序。
算法实现步骤
- 确定排序趟次，即确定最大的数的位数
- 从最低位按照分配和收集进行排序，直至最高位。
- 在每一趟，分配按照相应关键字的曲子将记录加入到r个不同的队列，收集是从小到大以此将r个队列收尾相接成数组。
算法流程图
基数排序
从图片可以看出，最大的数只有3位，进行3趟排序。先从个位进行排序，第二趟对十位数进行排序，最后对百位数进行排序。
Java代码实现
/**
* 基数排序
*
* @param nums
*/
public static void radixSort(int []nums){
//确定排序趟次
int time = sortTime(nums);
//建立10个队列
List<ArrayList> queue = new ArrayList<ArrayList>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> queue1 = new ArrayList<Integer>();
queue.add(queue1);
}
//进行time次分配和收集
for (int i = 0; i < time; i++) {
//分配数组元素;
for (int j = 0; j < nums.length; j++) {
//得到数字的第time+1位数
//先取余,再做除法
int x = nums[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue2 = queue.get(x);
queue2.add(nums[j]);
queue.set(x, queue2);
}
//元素计数器
int count = 0;
//收集队列元素
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
//如果该队列有分配到元素,对其进行收集
ArrayList<Integer> queue3 = queue.get(k);
nums[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
//查看第N趟排序后的结果
/*
System.out.print("\n"+"第"+i+"趟排序结果:");
for(int m=0;m<nums.length;m++){
System.out.print(nums[m]+" ");
}
*/
}
}
/**
* 计算基数排序的遍历趟次
*
* @param nums 待排序序列
* @return 返回一个int类型,表示需要遍历的趟次
*/
public static int sortTime(int []nums){
//首先确定排序的趟数
//通过待排序列的最大数来确定趟数time
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
int time = 0;
//判断位数;
while (max > 0) {
max /= 10;
time++;
}
return time;
}
算法分析
- 时间复杂度
- 最佳、最坏、平均：O(mn)
- 空间复杂度:O(n)
- 稳定性:稳定
总结
| 算法 | 平均复杂度 | 最佳时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n²) | O(n) | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(n) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | n(n^2) | O(nlogn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 基数排序 | O(nm) | O(nm) | O(nm) | O(n) | 稳定 |
