—————————文中的部分代码思路参考自《大话数据结构》一书。
目录
冒泡排序
插入排序
希尔排序
堆排序
选择排序
归并排序
快速排序
冒泡排序
原始的冒泡排序是对整个序列相邻两数字间重复做循环，并未考虑的序列实际的有序情况，而对冒泡排序的分析可知，若某一趟排序完成后没有相邻元素的交换即说明序列已经有序，可以结束循环，从而大大缩减运行时间，所以优化后的冒泡排序该设置一个“交换标记”，来促成循环的结束。
#include <stdio.h>#include <stdbool.h>#define arr_len 8void Swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}void BubbleSort(int a[]){int i, j;bool flag = true;//交换标记 for(i=1;i<arr_len && flag;i++){flag = false;//每趟初始化false，若无交换则会退出循环 for(j=1;j<=arr_len-i;j++){if(a[j]>a[j+1]){Swap(&a[j],&a[j+1]);flag = true;}}}}void main(){int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};int i;BubbleSort(arr);for(i=1;i<=arr_len;i++){printf("%d\t", arr[i]);}}
冒泡排序是一种稳定的算法，其平均时间复杂度为O(n^2)，最好情况下为O(n)，最坏情况下为O(n^2)，辅助空间为O(1)。
插入排序
插入排序即初始时认为序列的第一个元素是个有序的子列，然后循环从第二个元素开始，比较a[i]和子列最后一个元素a[i-1]，若满足a[i] < a[i-1]则将a[i]插入到子列合适的位置，否则直接将a[i]视为新子列最后一个元素，重复上述过程直到遍历至序列最后一个数， 代码比较好写。
import java.util.Scanner;public class Main {public static void InsertSort(int[] a, int n){for (int i = 1; i < n; i++) { //初始a[0]已经有序if (a[i] < a[i - 1]){ //进行插入，区间为[0,i]int t = a[i]; //哨兵int j;for (j = i - 1;j >= 0 && a[j] > t; j --) a[j + 1] = a[j]; //往后挪//此时a[j] <= t <= a[j + 1]a[j + 1] = t;}}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = in.nextInt();}InsertSort(a, n);for (int i = 0; i < n; i++) {System.out.print(a[i] + " ");}}}
简单插入排序是一种稳定的排序，平均、最好、最坏情况下的时间复杂度均为O(n^2)，辅助空间为O(1)，当序列基本有序时选用插入排序可使效率达到最高。
希尔排序
希尔排序是一种结合了插入排序的排序方法，其核心是给序列分成几个小块，在小块内排序，逐步使得序列基本有序，再利用插入排序的性质，此时性能相比大部分的O(n^2)类排序算法有很大提升。
#include <stdio.h>#include <stdbool.h>#define arr_len 8void ShellSort(int a[]){int i, j;int increment=4;do{increment--;//增量序列设置为3、2、1//插入排序的变形 for(i=1+increment;i<=arr_len;i++){if(a[i]<a[i-increment]){if(a[i]<a[i-increment]){a[0]=a[i];for(j=i-increment;j>0 && a[j]>a[0];j-=increment)//多一步对j的判断是否为正 a[j+increment]=a[j];a[j+increment]=a[0]; }}}}while(increment!=1);}void main(){int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};int i;ShellSort(arr);for(i=1;i<=arr_len;i++){printf("%d\t", arr[i]);}}
希尔排序是一种不稳定的排序，平均情况下时间复杂度为O(nlogn~n^2)，最好情况时为O(n^1.3)，最坏情况下为O(n^2)，辅助空间为O(1)。
堆排序
堆排序首先建立了大根堆大根堆这样一个概念，假想着将序列表示成一个堆(实际并没有真正构造出一棵树形结构)，每次筛选堆得到最大元素后将其与尾结点交换并脱离出去，这样一趟就得到“最大元素”的最终位置，重复筛选即得到有序序列。
#include <stdio.h>#include <stdbool.h>#define arr_len 8void Swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}//调整序列使a[s..m]为大根堆 void HeapAdjust(int a[], int s, int m){int temp, j;temp=a[s];for(j=2*s;j<=m;j*=2){//沿较大孩子结点向下筛选 //j从s的左孩子开始，经过筛选始终置为较大元素的下标 if(j<m && a[j]<a[j+1])//左孩子小于右孩子 j++;//右孩子较大，所以j移动到该位置 if(temp>=a[j])break;//s为根结点，与其左右孩子构成大根堆，无需调整 a[s]=a[j];s=j;//与for以外的a[s]=temp配合完成根与孩子的交换 }a[s]=temp;}//函数本体 void HeapSort(int a[]){int i;for(i=arr_len/2;i>=1;i--){//初始化大根堆 HeapAdjust(a,i,arr_len);}for(i=arr_len;i>1;i--){Swap(&a[1],&a[i]);//大根堆的根结点与尾结点交换 HeapAdjust(a,1,i-1);//调节除尾结点后的根堆 }}void main(){int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};int i;HeapSort(arr);for(i=1;i<=arr_len;i++){printf("%d\t", arr[i]);}}
堆排序是一种不稳定的排序，其平均、最好、最坏情况下的时间复杂度均为O(nlogn)，辅助空间为O(1)，适用于快速确定出序列中较大(小)元素的最终位置。
选择排序
选择排序应该是提到的几种排序方法中思路最简单且易理解的一种排序法，其核心就是从第一个元素开始向后，逐步选择出需要放在该位置的元素，即第一个位置找到最小元素、第二个位置找到次小元素、第三个位置找到倒数第三小的元素......。
#include <stdio.h>#include <stdbool.h>#define arr_len 8void Swap(int *a, int *b){int temp;temp = *a;*a = *b;*b = temp;}SelectSort(int a[]){int i, j, k;for(i=1;i<arr_len;i++){k=i;//记录最小值的下标for(j=i+1;j<=arr_len;j++){if(a[j]<a[k]){k=j;}}if(k!=i)Swap(&a[k],&a[i]);}}void main(){int arr[arr_len+1]={0,52,86,43,31,95,7,89,42};int i;SelectSort(arr);for(i=1;i<=arr_len;i++){printf("%d\t", arr[i]);}}
简单选择排序是一种稳定的算法，其平均、最好、最坏情况下的时间复杂度均为O(n^2)，辅助空间为O(1)。
归并排序
归并排序的核心思路就是分而治之，将待排序的序列从中间一分为二，再将分出的两个子序列又一分为二，重复下去直至所有子列长度为1时为止，这时每个子列可视为一个有序的序列，然后再将子列按从小到大的顺序归并为一个更大的序列(按照分割时的配对情况)，重复下去直至归并后的序列长度为原序列长度，这时得到的序列有序。
import java.util.Scanner;public class Main {private static int[] a = new int[100010];private static int[] temp = new int[100010]; //存左和右子序列的合并结果public static void MergeSort(int[] a, int l, int r){if (l >= r)return;int mid = l + r >> 1;MergeSort(a, l, mid); MergeSort(a, mid + 1, r); //拆分int cnt = 0;int i = l, j = mid + 1;//合并while (i <= mid && j <= r){if (a[i] > a[j]) temp[cnt ++] = a[j ++];elsetemp[cnt ++] = a[i ++];}while (i <= mid) temp[cnt ++] = a[i ++];while (j <= r)temp[cnt ++] = a[j ++];//更新原数组for(i = l, j = 0;i <= r;i ++, j ++)a[i] = temp[j];}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();for (int i = 0; i < n; i++) a[i] = in.nextInt();MergeSort(a, 0, n - 1);for(int i = 0;i < n;i ++)System.out.print(a[i] + " ");}}
归并排序的效率是很高的，但缺点就是需要的内存相比其他几种算法要多。归并排序是一种稳定的算法，其平均、最坏、最好的时间复杂度均为O(nlogn)，辅助空间为O(n)。
除此之外，还有一道很经典的题目可以考虑归并排序做👇👇
剑指 Offer 51. 数组中的逆序对
对应代码如下，主要在a[i] > a[j]时做一个统计。
import java.util.Scanner;class Solution {private static int[] temp = new int[100010]; //存左和右子序列的合并结果private static int count;public static void MergeSort(int[] a, int l, int r){if (l >= r)return;int mid = l + r >> 1;MergeSort(a, l, mid); MergeSort(a, mid + 1, r); //拆分int cnt = 0;int i = l, j = mid + 1;//合并while (i <= mid && j <= r){if (a[i] > a[j]){ //a[i] > a[j]时满足逆序对的性质，可以统计起来count += mid - i + 1; //左边位于i后面的元素全都 > a[i]，所以也 > a[j]temp[cnt ++] = a[j ++];}else{temp[cnt ++] = a[i ++];}}while (i <= mid) temp[cnt ++] = a[i ++];while (j <= r)temp[cnt ++] = a[j ++];//更新原数组for(i = l, j = 0;i <= r;i ++, j ++)a[i] = temp[j];}public int reversePairs(int[] nums) {int n = nums.length;count = 0;MergeSort(nums, 0, n - 1);return count;}}
快速排序
快速排序的算法利用的是双指针，其核心思想就是每趟排序确定一个序列元素pivotkey的最终位置，通常选序列中的第一个元素作为这个元素，然后比pivotkey小的都置于左边，比pivotkey大的都置于右边，接着对两边又作快速排序，重复下去直到某趟排序后pivotkey的左右序列均只有一个元素位置，容易想到用递归来实现该算法。
import java.util.Scanner;public class Main {public static void QuickSort(int[] a, int l, int r){if (l >= r)return;int pivot = a[l + r >> 1];//中间的值作为pivotint i = l, j = r;while (i < j) {//找不满足要求的i、jwhile (a[i] < pivot) i ++;while (a[j] > pivot) j --;if (i < j){//swapint t = a[i];a[i] = a[j];a[j] = t;}}//while循环结束后，q[l..j] <= pivot,q[j+1..r] >= pivotQuickSort(a, l, j);QuickSort(a, j + 1, r);}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = in.nextInt();}QuickSort(a, 0, n - 1);for (Integer i : a){System.out.print(i + " ");}}}
快速排序是一种不稳定的算法，其平均、最好情况的时间复杂度均为O(nlogn)，最坏情况为O(n^2)，辅助空间为O(logn)~O(n)。
