一、插入排序
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
public static void main(String[] s) {
int[] array = {3,1,6,0,8};
//循环的次数，也监控着每一轮开始key的位置
for (int i = 0; i < array.length - 1; i++) {
int key = array[i + 1];
int j;
//一边比较一边为key的插入腾空位
for (j = i; j >= 0 && key < array[j]; j--) {
array[j + 1] = array[j];
}
array[j + 1] = key;
}
System.out.println(Arrays.toString(array));
}
二、希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
public static void main(String[] args) {
int[] arr = {3,1,6,0,8};
//step:步长
for (int step = arr.length / 2; step > 0; step /= 2) {
//对一个步长区间进行比较 [step,arr.length)
for (int i = step; i < arr.length; i++) {
int value = arr[i];
int j;
//对步长区间中具体的元素进行比较
for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
//j为左区间的取值，j+step为右区间与左区间的对应值。
arr[j + step] = arr[j];
}
//此时step为一个负数，[j + step]为左区间上的初始交换值
arr[j + step] = value;
}
}
System.out.println(Arrays.toString(arr));
}
三、选择排序
1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3）重复第二步，直到所有元素均排序完毕。
public static void main(String[] args) {
int[] arr = {3,1,6,0,8};
for (int i = 0; i < arr.length; i++) {
// 将当前下标定义为最小值下标
int minIndex = i;
for (int j = i+1; j <arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
//如果不是同一个，就交换
if (i != minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
四、冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
public static void main(String[] args) {
int[] arr = {3,1,6,0,8};
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
五、归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
public static void main(String[] args) {
int[] a = {3,1,6,0,8};
int[] temp = new int[a.length];
diao(a, 0, a.length-1,temp);
System.out.println(Arrays.toString(a));
}
/**
* 分和合 的方法
* @param arr 原数组
* @param left 左部分的开始
* @param right 右部分的结束
* @param temp 临时数组
*/
public static void diao(int[] arr, int left, int right, int[] temp) {
if (left >= right) {//如果左大于等于右 说明到合并方法时只剩下一部分了,没有对比 自然不能发生比较排序
return;
}
int mid = (left + right) / 2;//中间索引
diao(arr, left, mid, temp);//左递归分
diao(arr, mid + 1, right, temp);//右递归分解
mergeSort(arr, left, mid, right, temp);//分解完 两部分比较 排序插入数组
}
/**
* 合并方法
* @param arr
* @param left
* @param mid
* @param right
* @param temp
*/
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;//记录左部分开头
int j = mid + 1;//右部分开头 同时也是左部分结束
int index = 0;//辅助下标
while (i <= mid && j <= right) {//如果左右开头部分 没到各自结尾 就继续合并 直到一部分处理完毕
//如果左边小于右边 将左边添加到temp
//同时 index++ i++
if (arr[i] <= arr[j]) {
temp[index] = arr[i];
index++;
i++;
} else {//反之 index++ j++
temp[index] = arr[j];
index++;
j++;
}
}
//当 两部分有一个处理完毕 剩下一个 将剩下部分的数字 全部填入temp
while (i <= mid) {
temp[index] = arr[i];
index++;
i++;
}
while (j <= right) {
temp[index] = arr[j];
index++;
j++;
}
//将temp数组部分拷贝到 arr
//注意不是 temp全部拷贝 而是没次调用合方法中 比较的两个部分的数字 拷贝
//第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3
//最后一次 tempLeft = 0 right = 7
index = 0;
int arrIndex=left;
while (arrIndex <= right) {
arr[arrIndex] = temp[index++];
arrIndex++;
}
}
六、快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
public static void main(String[] args) {
int[] arr = {3, 1, 6, 0, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
//temp就是基准位
temp = arr[low];
while (i < j) {
//先看右边，依次往左递减
while (temp <= arr[j] && i < j) {
j--;
}
//再看左边，依次往右递增
while (temp >= arr[i] && i < j) {
i++;
}
//如果满足条件则交换
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j - 1);
//递归调用右半数组
quickSort(arr, j + 1, high);
}
七、堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
public static void main(String[] args) {
int[] arr = {3, 1, 6, 0, 8};
headSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 堆排序
*/
public static void headSort(int[] list) {
//构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
for (int i = (list.length) / 2 - 1; i >= 0; i--) {
headAdjust(list, list.length, i);
}
//排序，将最大的节点放在堆尾，然后从根节点重新调整
for (int i = list.length - 1; i >= 1; i--) {
int temp = list[0];
list[0] = list[i];
list[i] = temp;
headAdjust(list, i, 0);
}
}
private static void headAdjust(int[] list, int len, int i) {
int k = i, temp = list[i], index = 2 * k + 1;
while (index < len) {
if (index + 1 < len) {
if (list[index] < list[index + 1]) {
index = index + 1;
}
}
if (list[index] > temp) {
list[k] = list[index];
k = index;
index = 2 * k + 1;
} else {
break;
}
}
list[k] = temp;
}
八、基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
public static void main(String[] args){
//定义整型数组
int[] arr = {3, 1, 6, 0, 8};
radixSort(arr, getMaxWeishu(arr));
//调用基数排序函数
System.out.println(Arrays.toString(arr));
}
//pos=1表示个位，pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
//求得最大位数d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else {
break;
}
}
return d;
}
public static void radixSort(int[] a, int d) {
int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;// array[i][0]记录第i行数据的个数
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {// 分配过程
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {// 收集过程
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;// 复位，下一个pos时还需使用
}
}
}
总结
各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：
image.png
网友评论