image.png
选择排序
每次循环找出最小数然后依次排序。
1、第0个数比对第1-N个数找到最小数，
2、第1个比对第2-N个数找到最二小数，
3、第2个比对第3-N个数找到最三小数，
。。。。
/**
* 选择排序
*
* @param array
* @return
*/
public static int[] selectSort(int[] array) {
if (array == null || array.length == 0) {
throw new NullPointerException("array is not null");
}
for (int i = 0, length = array.length; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
冒泡排序
对要排序的数据，从上到下依次比较两个相邻的数并加以调整，将最大的数向下移动，较小的数向上冒起。即：每一趟依次比较相邻的两个数据元素，将较小的数放在左边，循环进行同样的操作，直到全部待排序的数据元素排完.
-
第一趟排序
第一趟排序 -
第二趟排序
第二趟排序 - 第三趟。。。。
/**
* 冒泡排序bubble sort
*
* @param array
* @return
*/
public static int[] bubbleSort(int[] array) {
if (array == null || array.length == 0) {
throw new NullPointerException("array is not null");
}
for (int i = array.length - 1; i > 0; i--) {
//比较length-1趟
for (int j = 0; j < i; j++) {
//比较相邻数字大小
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
插入排序
每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
以数组{38,65,97,76,13,27,49}为例，
image.png
/**
* 插入排序
*
* @param array
* @return
*/
public static int[] insertSort(int[] array) {
for (int i = 1, length = array.length; i < length; i++) {
int temp = array[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (array[j] > temp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = temp;
}
return array;
}
选择排序，冒泡排序，插入排序区别:
1、选择排序是一个比对整个数组找到最小值
2、冒泡排序，是比较隔壁找到最小值
3、插入排序，是比对一排，然后插入位置，后面往后移。
image.png
归并排序
/**
* 归并排序
* @param array IntArray
* @param low Int
* @param high Int
*/
fun mergerSort(array: IntArray, low: Int, high: Int) {
val mid: Int = (low + high) / 2
if (low < high) {
mergerSort(array, low, mid)
mergerSort(array, mid + 1, high)
merge(array, low, mid, high)
}
}
private fun merge(array: IntArray, low: Int, mid: Int, high: Int) {
var temp: IntArray = IntArray(high - low + 1)
var i = low
var j = mid + 1
var k = 0
while (i <= mid && j <= high) {
if (array[i] < array[j]) {
temp[k] = array[i]
i++
} else {
temp[k] = array[j]
j++
}
k++
}
while (i <= mid) {
temp[k++] = array[i++]
}
while (j <= high) {
temp[k++] = array[j++]
}
for (k2 in temp.indices) {
array[k2 + low] = temp[k2]
}
}
快速排序
线性排序
桶排序：
桶排序比较适合用在外部排序中，所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中.(数值大小为整数，并相对不大)
计数排序
（数值大小为整数，并相对不大或者数值大小确定)
// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找数组中数据的范围
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 计算每个元素的个数，放入 c 中
for (int i = 0; i < n; ++i) {
c[a[i]]++;
}
// 依次累加
for (int i = 1; i <= max; ++i) {
c[i] = c[i-1] + c[i];
}
// 临时数组 r，存储排序之后的结果
int[] r = new int[n];
// 计算排序的关键步骤，有点难理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 将结果拷贝给 a 数组
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
基数排序
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
堆排序
希尔排序
排序复杂度
