一、選擇排序算法描述
- 初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空；
- 第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選 出關(guān)鍵字最小的記錄 R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R交換，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
- n-1趟結(jié)束，數(shù)組有序化了。
/**
* 選擇排序算法：最好、平均、最壞時(shí)間復(fù)雜度均為O(n2)，空間復(fù)雜度為1，穩(wěn)定性：不穩(wěn)
*/
static void selectSort(int[] arr) {
for (int j = 0; j < arr.length - 1; j++) {
int minPos = j;
for (int i = j + 1; i < arr.length; i++) {
if (arr[minPos] > arr[i]) {
minPos = i;
}
}
//交換起始位置和最小值的位置
swap(arr, j, minPos);
}
}
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
二、冒泡排序算法描述
- 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
- 對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
- 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
- 重復(fù)步驟1~3，直到排序完成。
/**
* 冒泡排序算法：最好時(shí)間復(fù)雜度為O(n)、平均、最壞時(shí)間復(fù)雜度均為O(n2)，空間復(fù)雜度為1，穩(wěn)定性：穩(wěn)
*/
static void bubbleSort(int[] arr) {
for (int j = 0; j < arr.length; j++) {
//遍歷數(shù)組，比較當(dāng)前值和后一個(gè)值，如果當(dāng)前值比后一個(gè)值大，則交換2個(gè)值的位置
for (int i = 0; i < arr.length - 1 - j; i++) {
if (arr[i] > arr[i + 1]) {
//交換2個(gè)元素的位置
swap(arr, i, i + 1);
}
}
}
}
三、插入排序算法描述
- 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
- 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；
- 重復(fù)步驟2~5。
/**
* 插入排序：最好時(shí)間復(fù)雜度為O(n)，平均、最壞時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為1，穩(wěn)定性：穩(wěn)
*/
static void insertionSort(int[] arr) {
//從第一個(gè)元素開(kāi)始，比較該元素與前一個(gè)元素
//如果該元素大于前一個(gè)元素，則將該元素放到該索引的位置，循換此步驟
for (int i = 1; i < arr.length; i++) {
//該數(shù)為遞減
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
//交換后一個(gè)元素和前一個(gè)元素的位置
swap(arr, j, j - 1);
} else {
break;
}
}
}
}
四、希爾排序（增量縮小排序）算法描述
- 選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；
- 每一趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度。
注意：希爾排序可能改變數(shù)據(jù)原本順序，所以不穩(wěn)定
/**
* 希爾排序：改進(jìn)的插入排序，最好時(shí)間復(fù)雜度O(n)，平均時(shí)間復(fù)雜度O(n^1.3)，最壞時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度為1，穩(wěn)定性：不穩(wěn)
*/
static void shellSort(int[] arr) {
int h = 1;
while (h <= arr.length / 3) {
h = 3 * h + 1;
}
for (int gap = h; gap >= 1; gap = (gap - 1) / 3) {
for (int i = gap; i < arr.length; i++) {
for (int j = i; j >= gap; j -= gap) {
if (arr[j] < arr[j - gap]) {
swap(arr, j, j - gap);
}
}
}
}
}
五、歸并排序（遞歸思想）算法描述
- 把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
- 對(duì)這兩個(gè)子序列分別采用歸并排序；
- 將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
/**
* 歸并排序：最好、平均、最壞時(shí)間復(fù)雜度均為O(nlogn)，空間復(fù)雜度為O(n)，穩(wěn)定性：穩(wěn)
*/
static void mergeSort(int[] arr){
sort(arr,0 , arr.length - 1);
}
static void sort(int[] arr, int left, int right) {
//把數(shù)組切割然后調(diào)用merge排序，直到left==right為止
if(left == right) return;
//找出數(shù)組中間索引，將數(shù)組分成2段分別排序
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
//將這2段數(shù)據(jù)進(jìn)行排序歸并
merge(arr, left, mid + 1, right);
}
static void merge(int[] arr, int left, int right, int rightBound) {
//將一個(gè)數(shù)組分為2段，把每一段數(shù)組進(jìn)行排序
int mid = right - 1;
int[] temp = new int[rightBound - left + 1];
//左邊數(shù)組起點(diǎn)
int leftPtr = left;
//右邊數(shù)組起點(diǎn)
int rightPtr = right;
//新數(shù)組起點(diǎn)
int k = 0;
while (leftPtr <= mid && rightPtr <= rightBound) {
temp[k++] = arr[leftPtr] <= arr[rightPtr] ? arr[leftPtr++] : arr[rightPtr++];
}
//將剩下的數(shù)組直接放到temp中
while (leftPtr <= mid) temp[k++] = arr[leftPtr++];
while (rightPtr <= rightBound) temp[k++] = arr[rightPtr++];
//temp完成后給傳入的數(shù)組賦值
System.arraycopy(temp, 0, arr, left, temp.length);
}
六、快速排序算法描述
- 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）；
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
/**
* 快速排序：最好、平均時(shí)間復(fù)雜度均為O(nlogn)，最壞時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(logn)，穩(wěn)定性：不穩(wěn)
*/
static void quickSort(int[] arr, int leftPtr, int rightBound) {
if(leftPtr >= rightBound) return;
//定義軸的索引
int pivotIndex = partition(arr, leftPtr, rightBound);
quickSort(arr, leftPtr, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, rightBound);
}
static int partition(int[] arr, int leftPtr, int rightBound) {
//以最右邊的數(shù)為軸,數(shù)組兩段同時(shí)向中間擠壓
int pivot = arr[rightBound];
int leftIndex = leftPtr;
int rightIndex = rightBound - 1;
//注意：這里的等于是為了最后索引交匯時(shí)，把leftIndex移到rightBound的位置
while (leftIndex <= rightIndex) {
//從左邊開(kāi)始，找到比軸數(shù)大的數(shù)為止
while (leftIndex <= rightIndex && arr[leftIndex] <= pivot) leftIndex++;
//從右邊開(kāi)始，找到比軸數(shù)小的數(shù)為止
while (leftIndex <= rightIndex && arr[rightIndex] > pivot) rightIndex--;
//如果索引沒(méi)有交叉，則交換兩個(gè)位置的數(shù)
if(leftIndex < rightIndex) swap(arr, leftIndex, rightIndex);
}
//將軸上的值放到該數(shù)本該處的位置
swap(arr, leftIndex, rightBound);
return leftIndex;
}
七、計(jì)數(shù)排序算法描述
- 找出待排序的數(shù)組中最大和最小的元素；
- 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)；
- 對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）；
- 反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1。
/**
* 計(jì)數(shù)排序：最好、平均、最壞時(shí)間復(fù)雜度均為O(n + k)，空間復(fù)雜度為O(n + k)，穩(wěn)定性：穩(wěn)
*/
static void countingSort(int[] arr) {
int bucketLen = findMax(arr) + 1;
int[] bucket = new int[bucketLen];
//count中，下標(biāo)即為數(shù)字本身，下標(biāo)上的值即為該數(shù)字的數(shù)量
for (int value : arr) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
//將計(jì)數(shù)數(shù)組挨個(gè)遞減直到0為止
while (bucket[j] > 0) {
//把原數(shù)組重新賦值
arr[sortedIndex++] = j;
//賦值后計(jì)數(shù)數(shù)組當(dāng)前索引上的值自減
bucket[j]--;
}
}
}
static int findMax(int[] arr) {
int result = arr[0];
for (int i = 0; i < arr.length; i++) {
result = Math.max(result, arr[i]);
}
return result;
}
八、基數(shù)排序算法描述
- 取得數(shù)組中的最大數(shù)，并取得位數(shù)；
- arr為原始數(shù)組，從最低位開(kāi)始取每個(gè)位組成radix數(shù)組；
- 對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）；
/***
* 基數(shù)排序：最好、平均、最壞時(shí)間復(fù)雜度均為O(n * k)，空間復(fù)雜度為O(n + k)，穩(wěn)定性：穩(wěn)
* @return
*/
static int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
//最高有幾位就循環(huán)幾次
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考慮負(fù)數(shù)的情況，這里擴(kuò)展一倍隊(duì)列數(shù)，其中 [0-9]對(duì)應(yīng)負(fù)數(shù)，[10-19]對(duì)應(yīng)正數(shù) (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自動(dòng)擴(kuò)容，并保存數(shù)據(jù)
*
* @param arr
* @param value
*/
static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
/**
* 獲取最高位數(shù)
*/
static int getMaxDigit(int[] arr) {
int maxValue = findMax(arr);
return getNumLenght(maxValue);
}
//獲取數(shù)字位數(shù)，幾位數(shù)
static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
九、桶排序算法描述
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
- 對(duì)每個(gè)不是空的桶進(jìn)行排序；
- 從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)。
/***
* 桶排序：最好時(shí)間復(fù)雜度均為O(n)，平均時(shí)間復(fù)雜度均為O(n + k)，最壞時(shí)間復(fù)雜度均為O(n2)，空間復(fù)雜度為O(n + k)，穩(wěn)定性：穩(wěn)
*/
static int[] bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrayAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 對(duì)每個(gè)桶進(jìn)行排序，這里使用了插入排序
bucket = insertionSort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
