選擇排序
每次循環(huán)找出最小數(shù)然后依次排序。
1凿将、第0個(gè)數(shù)比對(duì)第1-N個(gè)數(shù)找到最小數(shù)年鸳，
2、第1個(gè)比對(duì)第2-N個(gè)數(shù)找到最二小數(shù)丸相，
3搔确、第2個(gè)比對(duì)第3-N個(gè)數(shù)找到最三小數(shù)，
。膳算。座硕。。
/**
* 選擇排序
*
* @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;
}
冒泡排序
對(duì)要排序的數(shù)據(jù)涕蜂，從上到下依次比較兩個(gè)相鄰的數(shù)并加以調(diào)整华匾，將最大的數(shù)向下移動(dòng)，較小的數(shù)向上冒起机隙。即：每一趟依次比較相鄰的兩個(gè)數(shù)據(jù)元素蜘拉，將較小的數(shù)放在左邊，循環(huán)進(jìn)行同樣的操作有鹿，直到全部待排序的數(shù)據(jù)元素排完.
-
第一趟排序
第一趟排序 -
第二趟排序
第二趟排序 - 第三趟旭旭。。葱跋。持寄。
/**
* 冒泡排序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++) {
//比較相鄰數(shù)字大小
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
return array;
}
插入排序
每步將一個(gè)待排序的記錄，按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后）娱俺，直到全部插入排序完為止稍味。
以數(shù)組{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;
}
選擇排序荠卷，冒泡排序模庐，插入排序區(qū)別:
1、選擇排序是一個(gè)比對(duì)整個(gè)數(shù)組找到最小值
2油宜、冒泡排序掂碱，是比較隔壁找到最小值
3、插入排序验庙，是比對(duì)一排顶吮，然后插入位置，后面往后移粪薛。
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]
}
}
快速排序
線性排序
桶排序：
桶排序比較適合用在外部排序中悴了，所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤中，數(shù)據(jù)量比較大违寿，內(nèi)存有限湃交，無法將數(shù)據(jù)全部加載到內(nèi)存中.(數(shù)值大小為整數(shù)，并相對(duì)不大)
計(jì)數(shù)排序
（數(shù)值大小為整數(shù)藤巢，并相對(duì)不大或者數(shù)值大小確定)
// 計(jì)數(shù)排序搞莺，a 是數(shù)組，n 是數(shù)組大小掂咒。假設(shè)數(shù)組中存儲(chǔ)的都是非負(fù)整數(shù)才沧。
public void countingSort(int[] a, int n) {
if (n <= 1) return;
// 查找數(shù)組中數(shù)據(jù)的范圍
int max = a[0];
for (int i = 1; i < n; ++i) {
if (max < a[i]) {
max = a[i];
}
}
int[] c = new int[max + 1]; // 申請(qǐng)一個(gè)計(jì)數(shù)數(shù)組 c迈喉，下標(biāo)大小 [0,max]
for (int i = 0; i <= max; ++i) {
c[i] = 0;
}
// 計(jì)算每個(gè)元素的個(gè)數(shù)，放入 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];
}
// 臨時(shí)數(shù)組 r温圆，存儲(chǔ)排序之后的結(jié)果
int[] r = new int[n];
// 計(jì)算排序的關(guān)鍵步驟挨摸，有點(diǎn)難理解
for (int i = n - 1; i >= 0; --i) {
int index = c[a[i]]-1;
r[index] = a[i];
c[a[i]]--;
}
// 將結(jié)果拷貝給 a 數(shù)組
for (int i = 0; i < n; ++i) {
a[i] = r[i];
}
}
基數(shù)排序
基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的，需要可以分割出獨(dú)立的“位”來比較岁歉，而且位之間有遞進(jìn)的關(guān)系得运，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大，那剩下的低位就不用比較了锅移。除此之外熔掺，每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序算法來排序非剃，否則置逻，基數(shù)排序的時(shí)間復(fù)雜度就無法做到 O(n) 了。
堆排序
希爾排序
