八大排序算法
前言
| 算法名称 | 分类 | 时间复杂度(最好情况) | 时间复杂度(平均情况) | 时间复杂度(最坏情况) | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|---|
| 直接插入排序 | 插入排序 | O(n) | O(n2) | O(n2) | O(1) | 是 |
| 冒泡排序 | 交换排序 | O(n) | O(n2) | O(n2) | O(1) | 是 |
| 简单选择排序 | 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 否 |
| 希尔插入排序 | 插入排序 | – | – | – | O(1) | 否 |
| 快速排序 | 交换排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(log2n) | 否 |
| 堆排序 | 选择排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 否 |
| 2-路归并排序 | 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 是 |
| 基数排序 | 基于关键字排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O( r ) | 是 |
1. 插入排序
1.1 直接插入排序
//直接插入排序,从小到大 ，平均性能O(n2)
public static void InsertSort(int[] list) {
int key = 0; //哨兵位
int i, j;
//第0位已经是完成排序，从第1位开始遍历
for (i = 1; i < list.length; i++) {
if (list[i] < list[i - 1]) {
key = list[i];
for (j = i - 1; j >= 0 && list[j] > key; j--) {
list[j + 1] = list[j]; //往后移动位置，直到找到i该放置的地方
}
list[j + 1] = key;
}
}
}
1.2 折半插入排序（直接插入的改进）
//在直接插入的基础上改进，折半插入排序，平均性能O(n2)，只是减少了比较的次数
public static void BinaryInsertSort(int[] list) {
int key, i, j, low, high, mid = 0;
for (i = 1; i < list.length; i++) {
if (list[i] < list[i - 1]) {
low = 0;
high = i - 1;
key = list[i];
while (low <= high) { //折半查找。默认左侧已经递增有序
mid = (low + high) / 2; //取中间点
if (list[mid] < key)
low = mid + 1; //查找右半边
else
high = mid - 1; //查找左半边
}
for (j = i - 1; j >= high + 1; j--)
list[j + 1] = list[j];
list[high + 1] = key;
}
}
}
1.3 希尔插入排序(shell排序/缩小增量排序)
//希尔插入排序,根据步长而定，约等于O(n2)
public static void ShellInsertSort(int[] list) {
int dk, i, j, key;
for (dk = list.length / 2; dk > 0; dk /= 2) {
for (i = dk; i < list.length; i++) {
if (list[i] < list[i - dk]) {
key = list[i];
for (j = i - dk; j >= 0 && list[j] > key; j -= dk)
list[j + dk] = list[j];
list[j + dk] = key;
}
}
}
}
2. 交换排序
2.1 冒泡排序
//冒泡排序|起泡排序,选择一个方向两两比较相邻元素的值，每趟起泡下来可以确定一个元素的最终位置
public static void BubbleSort(int[] list) {
int i, j, flag, temp;
for (i = 0; i < list.length; i++) {
flag = 0; //标记位
for (j = list.length - 1; j > i; j--) {
if (list[j] < list[j - 1]) { //进行交换操作
temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
flag = 1;
}
}
if (flag == 0) return; //表示这一趟没有交换，即已经有序，可以结束排序
}
}
2.2 快速排序
（对冒泡排序的一种改进，等会的测试中会看到提升了很大性能）
//快速排序，基于分治的思想，是对冒泡排序的一种改进
//每趟排序下来使基准左边的值都小于他，右边的值都大于他
public static void QuickSort(int[] list, int low, int high) {
int pivot; //划分点
if (low < high) { //跳出递归的条件
pivot = Partition(list, low, high); //获得划分点
QuickSort(list, low, pivot - 1); //左侧子表划分
QuickSort(list, pivot + 1, high); //右侧子表划分
}
}
//一趟排序过程，划分操作其实有很多版本，我这里取我学习时候的严版教材的
public static int Partition(int[] list, int low, int high) {
int key, i, j;
key = list[low]; //以第一个为基准点，以此为划分点
while (low < high) {
while (low < high && list[high] >= key) high--;
list[low] = list[high]; //将比基准点小的值移到左边
while (low < high && list[low] <= key) low++;
list[high] = list[low]; //将比基准点大的值移到右边
}
list[low] = key; //基准点最终被存放的位置
return low; //返回区分的坐标点，左侧都比他小，右侧都比他大
}
3. 选择排序
3.1 简单选择排序
//简单选择排序，每次把最大/最小的元素选出来，置于一侧
public static void SelectSort(int[] list) {
int min, i, j, temp;
for (i = 0; i < list.length; i++) {
min = i; //设置第一个元素为最小值
for (j = i + 1; j < list.length; j++)
if (list[j] < list[min]) min = j; //遍历找到最小的那个值
if (min != i) { //进行交换
temp = list[min];
list[min] = list[i];
list[i] = temp;
}
}
}
3.2 堆排序
//堆排序，比较复杂的一个排序，用于选出前a个最大/小的值比较合适
//刚开始建立大顶堆或者小顶堆，然后一次次的将堆顶元素和最后一个元素交换
//破坏堆结构再重新调整建堆，从第一个元素到第n-1个元素
//最后就得到了一个有序数列。即达到了排序的目的
//实际是一颗完全二叉树，一般都用数组来表示堆
//若从1开始 ，则i结点的父结点下标就为i/2，左右子结点下标分别为2*i和2*i+1
//若从0开始 ，则i结点的父结点下标就为(i–1)/2，左右子结点下标分别为2*i+1和2*i+2
//此处以从0开始为例，创造一个大顶堆（大顶堆得到升序，小顶堆得到逆序）
public static void HeapSort(int[] list) {
int i, j, key, temp;
//以大顶堆为例，初始化堆
//从i=0~[n/2],反复调整堆，不必从最后一个节点开始
// 因为完全二叉树，后半子表没有子节点，所以从中间开始遍历即可
for (i = list.length / 2 - 1; i >= 0; i--) {
AdjustDown(list, i, list.length);
}
//从后往前遍历，堆顶元素为最值元素
// 依次将堆顶元素和最后一个元素交换，达到排序目的
for (i = list.length -1; i > 0; i--) {
temp = list[i]; //堆顶元素和最后一个元素进行交换
list[i] = list[0];
list[0] = temp;
AdjustDown(list, 0, i ); //遍历调整
}
}
//将itr位置的元素向下调整
//itr是位置坐标，len是数组长度
public static void AdjustDown(int[] list, int itr, int len) {
int i, j, temp, key;
key = list[itr];
for (i = 2 * itr + 1; i < len; i = i * 2 + 1) {
if (i+1 < len && list[i] < list[i + 1]) i++; //取较大的子节点
if (key >= list[i]) break; //比子节点要大，遍历结束
else {
list[itr] = list[i]; //将值往下走
itr = i;
}
}
list[itr]=key; //赋值回去
}
4. 归并排序和基数排序
4.1 2路-归并排序
//归并排序，将数组分成好几列，分别排序再整合
// 这里以2路为例，每两个为一组进行排序
public static void MergeSort(int[] list, int low, int high) {
if (low < high) {
int mid = (low + high) / 2; //取中间点
MergeSort(list, low, mid); //左侧遍历排序
MergeSort(list, mid + 1, high); //右侧遍历排序
Merge(list, low, mid, high); //左右有序列表合并
}
}
static int[] tempList = new int[10000000]; //辅助数组
//合并方法，这里要用到辅助数组，所以空间复杂度O（n）
//现在左右两侧都已经是有序数组，需要合并
public static void Merge(int[] list, int low, int mid, int high) {
int i, j, k, key;
for (i = low; i <= high; i++) tempList[i] = list[i]; //辅助数组赋值
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
if (tempList[i] < tempList[j]) { //将较小值复制回去
list[k] = tempList[i++];
} else {
list[k] = tempList[j++];
}
}
while (i <= mid) list[k++] = tempList[i++]; //若左表没比较完，复制左表内容
while (j <= high) list[k++] = tempList[j++]; //若右表没比较完，复制右表内容
}
4.2 基数排序
// 基数排序，这个脑回路有点强。。不是基于比较进行排序，而是采用关键字排序思想
// 借助“分配”和“收集”两种操作对单逻辑关键字进行排序
public static void RadixSort(int[] list) {
int i, j, k, temp, max, exp;
for (i = 0, max = list[0]; i < list.length; i++)
if (list[i] > max) max = list[i]; //先获得数组的最大值，根据他来获得位数
for (exp = 1; max / exp > 0; exp *= 10)
RadixCount(list, exp); //从各位开始，对数组按exp进行排序
}
public static void RadixCount(int[] list, int exp) {
int i, j, k, temp, max;
int[][] outputs = new int[10][list.length]; //辅助数组, 十进制，0~9共10位
int[] buckets = new int[10];
//按第exp位划分,将对应的数据放进对应的桶
for (i = 0; i < list.length; i++) {
temp = (list[i] / exp) % 10;
outputs[temp][buckets[temp]++] = list[i];
}
//排序好的值赋值回去
for (i = 0, k = 0; i < buckets.length; i++)
for (j = 0; j < buckets[i]; j++, k++)
list[k] = outputs[i][j];
outputs = null; //赋值为null,更快地回收 变量的内存空间
buckets = null;
}
5. 时间比较
打完收工，运行下比较时间，这里取了几组小数据，一组是1000个数据，一组是10000个数据，卒子后一个500000。。其实后面几个排序就算是一亿个数据，也能在一分钟内解决，嗯，但是运行冒泡这些排序。。太耗时了，就不搞这么大了，读者可以自行尝试：
//测试程序
public static void main(String[] args) {
int[] list = new int[100000];
int[] list2;
long t1, t2;
for (int i = 0; i < list.length; i++)
list[i] = (int) (Math.random() * 1000000);
System.out.println("原始数据,共有" + list.length + "个数据：");
System.out.print("[");
// Arrays.stream(list).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
InsertSort(list2);
t2 = System.currentTimeMillis();
System.out.println("直接插入时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
BinaryInsertSort(list2);
t2 = System.currentTimeMillis();
System.out.println("折半插入时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
ShellInsertSort(list2);
t2 = System.currentTimeMillis();
System.out.println("希尔插入时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
BubbleSort(list2);
t2 = System.currentTimeMillis();
System.out.println("冒泡排序时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
QuickSort(list2, 0, list.length - 1);
t2 = System.currentTimeMillis();
System.out.println("快速排序时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
SelectSort(list2);
t2 = System.currentTimeMillis();
System.out.println("简单选择" +
"时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
HeapSort(list2);
t2 = System.currentTimeMillis();
System.out.println("大顶堆排序" +
"时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
MergeSort(list2, 0, list.length - 1);
t2 = System.currentTimeMillis();
System.out.println("2路归并排序" +
"时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
list2 = null;
list2 = list.clone();
t1 = System.currentTimeMillis();
RadixSort(list2);
t2 = System.currentTimeMillis();
System.out.println("基数排序" +
"时间耗时：" + (t2 - t1) + "ms:");
System.out.print("[");
// Arrays.stream(list2).forEach(o -> System.out.print(o + " "));
System.out.println("]");
}
1000个数据：
10000个数据：
500000个数据：