目錄
概念
插入排序
直接插入排序
希爾排序
選擇排序
直接選擇排序
雙向選擇排序
堆排序
交換排序
冒泡排序
快速排序
Hoare法
挖坑法
前后指針?lè)?/p>
快排的優(yōu)化
三數(shù)取中法
非遞歸快排
歸并排序
分治算法+二路歸并
非遞歸歸并
應(yīng)用
排序總結(jié)
其他排序
計(jì)數(shù)排序
簡(jiǎn)單版本
復(fù)雜版本（穩(wěn)定版本）
基數(shù)排序?
桶排序?
概念
排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性：假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過(guò)排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱(chēng)這種排序算法是穩(wěn)定的；否則稱(chēng)為不穩(wěn)定的。 ?
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。 （比如要放在磁盤(pán)，硬盤(pán)等來(lái)進(jìn)行排序）
分類(lèi)：
插入排序
直接插入排序
動(dòng)圖演示如下：
我們可以設(shè)置兩個(gè)指針i和j，i放在第二個(gè)元素的位置，j放在第一個(gè)元素的位置
每次把i位置的元素提取出來(lái)放到tmp中，和j位置的元素進(jìn)行比較，如果tmp的元素較小，就與j位置元素進(jìn)行交換
交換完之后j--，看看前面還有沒(méi)有元素比交換后靠前的元素大，如果有就重復(fù)上述步驟，沒(méi)有就把j和i挪到下一個(gè)元素
?
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}時(shí)間復(fù)雜度？
最壞情況：
假設(shè)有n個(gè)數(shù)據(jù)，遍歷第2個(gè)元素并進(jìn)行交換，j要回退2-1 = 1次
遍歷第3個(gè)元素并進(jìn)行交換，j要回退3-1 = 2次
遍歷第n個(gè)元素并進(jìn)行交換，j還需要進(jìn)行回退n-1次，那么需要n-1次操作，
總共就需要
1+2+3+...+n-1 ≈ n^2 -->O(n^2)
最好情況:
交換之后j不需要進(jìn)行回退，那么直直遍歷下去 --> O(n)
所以直插適用于：待排序序列基本趨于有序了
穩(wěn)定性？
直接插入排序是穩(wěn)定的，數(shù)據(jù)交換判斷需要array[i] > tmp才有進(jìn)行交換，如果原本序列有兩個(gè)相同的數(shù)字，那直插是不會(huì)改變這兩個(gè)數(shù)字的順序的，所以是穩(wěn)定的
?一個(gè)穩(wěn)定的排序可以通過(guò)修改條件變成不穩(wěn)定的排序，但是不穩(wěn)定的排序一定不能變成穩(wěn)定的排序
希爾排序
縮小增量排序，比如下面的排序
初始數(shù)據(jù)我們可以分成5組，此時(shí)的增量就是5，接著第1個(gè)元素與第6個(gè)元素，第2個(gè)元素與第7個(gè)元素等兩兩交換
接著降低增量（gap / 2），增加每組的數(shù)據(jù)，繼續(xù)進(jìn)行排序
其實(shí)前面的增量分組相當(dāng)于一個(gè)預(yù)排序，真正的排序是最后一組
//希爾排序
public static void shellSort(int[] array){
int gap = array.length;
while(gap>1){
gap /= 2;
shell(array,gap);
}
}
/**
* 對(duì)每組進(jìn)行排序
* 這段代碼其實(shí)跟插入排序差不多，就是i其實(shí)位置在gap上，j每次遞減遞增gap個(gè)單位
* @param array
* @param gap
*/
public static void shell(int[] array, int gap){
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i -gap;
for (; j >= 0 ; j-=gap) {
if (array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}時(shí)間復(fù)雜度？
穩(wěn)定性？不穩(wěn)定，因?yàn)榉纸M交換之后會(huì)打亂相同的數(shù)字原本的前后順序
編寫(xiě)個(gè)代碼來(lái)測(cè)試一下兩者的運(yùn)行時(shí)間
import java.util.Arrays;
public class Test {
public static void testInsert(int[] array){
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.insertSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("直接插入排序時(shí)間："+(endTime-startTime));
}
public static void testShell(int[] array){
int[] tmpArray = Arrays.copyOf(array, array.length);
long startTime = System.currentTimeMillis();
Sort.shellSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("希爾排序時(shí)間："+(endTime-startTime));
}
public static void initArray(int[] array){
for (int i = 0; i < array.length; i++) {
array[i] = array.length-i;
}
}
public static void main(String[] args) {
int[] array = new int[10_0000];
initArray(array);
testInsert(array);
testShell(array);
}
}
選擇排序
直接選擇排序
動(dòng)圖如下：
設(shè)置i和j，遍歷當(dāng)前i下標(biāo)后面的元素（j++），找到一個(gè)最小的值與i下標(biāo)的元素進(jìn)行替換
然后i++，進(jìn)行下一個(gè)元素的交換
/**
* 選擇排序
* 時(shí)間復(fù)雜度O(n^2)
* 空間復(fù)雜度O(1)
* 穩(wěn)定性：不穩(wěn)定
* @param array
* @param i
* @param j
*/
public static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex = i;
//j往后遍歷，每次找到比minIndex下標(biāo)元素小的就進(jìn)行下標(biāo)替換
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[minIndex]){
minIndex = j;
}
}
swap(array,i,minIndex);
}
}雙向選擇排序
設(shè)置最左邊下標(biāo)l和最右邊下標(biāo)r，設(shè)置i = l+1，往后遍歷，找到最小值的下標(biāo)和最大值的下標(biāo)
接著把minIndex的元素與l交換，maxIndex的元素與r交換
接著再i++，l++，r--，重復(fù)上面的步驟
注意：如果l的位置就是最大值，經(jīng)過(guò)與最小值交換之后不一定有序
所以我們要把minIndex和maxIndex換過(guò)來(lái)
public static void selectSort2(int[] array){
int left = 0;
int right = array.length-1;
while(left<right){
int minIndex = left;
int maxIndex = right;
//找到最大值和最小值下標(biāo)
for (int i = left+1; i <= right; i++) {
if(array[i] < array[minIndex]){
minIndex = i;
}
if(array[i] > array[maxIndex]){
maxIndex = i;
}
}
swap(array,minIndex,left);
if(maxIndex == left){
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}堆排序
可以看著我這篇博客的思路數(shù)據(jù)結(jié)構(gòu)：優(yōu)先級(jí)隊(duì)列（堆）-CSDN博客
代碼如下：
private static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
siftDown(array,parent,array.length);//alt+enter
}
}
private static void siftDown(int[] array,int parent, int length) {
int child = 2*parent + 1;
while (child < length) {
if(child+1 < length && array[child] < array[child+1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array,child,parent);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}
/**
* 時(shí)間復(fù)雜度：O(N*logN)
* 空間復(fù)雜度：O(1)
* 穩(wěn)定性：不穩(wěn)定的排序
* @param array
*/
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
交換排序
冒泡排序
動(dòng)圖如下：
/**
* 時(shí)間復(fù)雜度：O(n^2)
* 空間復(fù)雜度：O(1)
* 穩(wěn)定性：穩(wěn)定
* @param array
*/
public static void bubbleSort(int[] array){
//i代表趟數(shù)
for (int i = 0; i < array.length-1; i++) {
//每一趟都比較上一趟有沒(méi)有交換
boolean flg = false;
//j來(lái)比較每個(gè)數(shù)據(jù)的大小
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if(flg==false){
break;
}
}
}快速排序
Hoare法
單趟動(dòng)圖如下：
第一輪交換之后，6在中間，6的左邊都比6小，右邊都比6大
第二輪和第一輪一樣，接著不停地遞歸下去
這些數(shù)組可以拆分并組成一棵二叉樹(shù)如下圖，二叉樹(shù)就是左邊和右邊分別遞歸?
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array, int start, int end){
if(start >= end){
return;
}
//找到中間的值
int pivot = partitionHoare(array,start,end);
//左右分別進(jìn)行遞歸
quick(array,start,pivot-1);
quick(array,pivot+1,end);
}接下來(lái)我們要來(lái)搞定partition的方法，也就是要找到整個(gè)序列中間值
先確定第一個(gè)元素是pivot元素
right指針負(fù)責(zé)找到比array[right]小的數(shù)字，left指針負(fù)責(zé)找到比array[left]大的數(shù)字
找到了就進(jìn)行交換，直到左右指針相遇
private static int partitionHoare(int[] array, int left, int right){
int tmp = array[left];
int i = left;
//整個(gè)的循環(huán)，要求left和right相遇之后能交換數(shù)字
while(left<right){
//單獨(dú)的循環(huán)，因?yàn)槿绻鹯ight--一直找不到比tmp大的數(shù)，而right不能一直減到最左邊的邊界
//所以需要再規(guī)定依次left<right
while(left<right && array[right] >= tmp){
right--;
}
while (left<right && array[left] <= tmp){
left++;
}
swap(array,left,right);
}
swap(array,i,left);
return left;
}思考：
1.為什么這里要有一個(gè)等于號(hào)
如果不用=號(hào)可能會(huì)進(jìn)入死循環(huán)
如果沒(méi)有等于號(hào)，第一個(gè)循環(huán)因?yàn)?不大于6，right沒(méi)辦法--，同理left沒(méi)辦法++，走到后面right和left進(jìn)行交換，只是相當(dāng)于6和6這兩個(gè)元素的下標(biāo)進(jìn)行交換而已，整個(gè)數(shù)組也沒(méi)有進(jìn)行排序
2.為什么從右邊開(kāi)始而不是從左邊開(kāi)始？
如果先走左邊，有可能會(huì)出現(xiàn)相遇的時(shí)大的數(shù)據(jù)，最后把大的數(shù)據(jù)放在最前面
而先走右邊的話(huà)可以先遇到小的，可以把小的放到前面
時(shí)間復(fù)雜度？
最好情況：
根據(jù)上方代碼的遞歸分治思想，找到中間值，遞歸左邊遞歸右邊再出中間值，每次出一個(gè)中間值都是把一部分一分為二進(jìn)行尋找（logn）
每次循環(huán)都有n個(gè)元素要進(jìn)行遍歷
最后總的時(shí)間復(fù)雜度O(n*logn)
最壞情況：
比如：1 2 3 4 5
遞歸時(shí)right每次找到比1小的值都要遍歷n個(gè)元素，在循環(huán)中每次都要遍歷n個(gè)元素檢查是否進(jìn)行交換
所以總的時(shí)間復(fù)雜度就是O(n^2)
?快排使用時(shí)，數(shù)據(jù)一般不是逆序或者有序的
?快排使用時(shí)，往往會(huì)有棧的溢出
這個(gè)錯(cuò)誤跟我們遞歸的層次有關(guān)系，遞歸越多在棧上開(kāi)辟的空間就越多，而IDEA默認(rèn)給出的空間是256KB，這么小的空間容納不了我們10萬(wàn)個(gè)數(shù)據(jù)進(jìn)行棧空間的開(kāi)辟
我們要對(duì)IDEA進(jìn)行一個(gè)調(diào)整
挖坑法
單趟動(dòng)圖如下：
private static int partitionHole(int[] array, int left, int right){
int tmp = array[left];
//整個(gè)的循環(huán)，要求left和right相遇之后能交換數(shù)字
while(left<right){
//單獨(dú)的循環(huán)，因?yàn)槿绻鹯ight--一直找不到比tmp大的數(shù)，而right不能一直減到最左邊的邊界
//所以需要再規(guī)定依次left<right
while(left<right && array[right] >= tmp){
right--;
}
array[left] = array[right];
while (left<right && array[left] <= tmp){
left++;
}
array[right] = array[left];
swap(array,left,right);
}
array[left] = tmp;
return left;
}前后指針?lè)?/h4>
思路：
1、選出一個(gè)key，一般是最左邊或是最右邊的。
2、起始時(shí)，prev指針指向序列開(kāi)頭，cur指針指向prev+1。
3、若cur指向的內(nèi)容小于key，則prev先向后移動(dòng)一位，然后交換prev和cur指針指向的內(nèi)容，然后cur指針++；若cur指向的內(nèi)容大于key，則cur指針直接++。如此進(jìn)行下去，直到cur到達(dá)end位置，此時(shí)將key和++prev指針指向的內(nèi)容交換即可。
/**
* 前后指針?lè)ǎ? * 總結(jié)：
* 1. Hoare 優(yōu)先級(jí): 2
* 2. 挖坑法 優(yōu)先級(jí)：1
* 3. 前后指針?lè)?優(yōu)先級(jí)：3
* 這3種方式 每次劃分之后的前后順序 有可能是不一樣的
* @param array
* @param left
* @param right
* @return
*/
private static int partition(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
swap(array, prev, left);
return prev;
}選擇題：?
這道題不要太死板地做，題目問(wèn)我們第8個(gè)記錄45，那么說(shuō)明45之前的數(shù)字一定是有序的
那45就需要比較到比它小的數(shù)就行，很簡(jiǎn)單選C
快排的優(yōu)化
上面我們提到了，快排一旦遞歸較多的時(shí)候容易出現(xiàn)棧溢出的情況
所以我們優(yōu)化方向：1.減少遞歸次數(shù)；2.讓每一次都能均勻地分割數(shù)組
三數(shù)取中法
上面提到當(dāng)快排的hoare和挖坑法遇到有序數(shù)列時(shí)，l和r都跑到第一個(gè)元素去，右邊有一大坨數(shù)字，無(wú)法實(shí)現(xiàn)取到中間數(shù)的效果
我們采用三數(shù)取中法
1.先找到數(shù)列中間下標(biāo)（m）的數(shù)字
int mid = (left+right)/2;
定義大前提
?
2.找出l，m，r下標(biāo)的三個(gè)數(shù)字排在最中間的那個(gè)數(shù)
array[left]<array[right]
array[left]>array[right]
?
if(array[left] < array[right]){
if(array[mid]<array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
//array[left] > array[right]
if(array[mid]>array[left]){
return left;
}else if(array[mid] < array[right]){
return right;
}else{
return mid;
}
}3.把m坐標(biāo)元素與l坐標(biāo)元素交換
4.然后以4為基準(zhǔn)，利用r--找到比4小的元素，把這個(gè)元素與4交換
這樣就不會(huì)出現(xiàn)找不到左數(shù)或者右數(shù)的情況
5.接著左右子樹(shù)進(jìn)行遍歷就行了
if(start>=end){
return;
}
//1 2 3 4 5 6 7
int index = middleNum(array,start,end);
swap(array,index,start);
//4 2 3 1 5 6 7
int pivot = partition(array,start,end);
quick2(array,start,pivot-1);
quick2(array,pivot+1,end);6.排序的最終步驟一般集中在數(shù)組二叉樹(shù)的最后兩層，而當(dāng)排序到這個(gè)地方的時(shí)候，整個(gè)數(shù)組已經(jīng)偏向有序的狀態(tài)了，所以我們沒(méi)必要再讓二叉樹(shù)繼續(xù)遞歸下去，我們可以采用插入排序，在一個(gè)很小的序列中進(jìn)行排序。這樣可以降低樹(shù)的高度，減少遞歸的次數(shù)
整個(gè)的代碼
private static int middleNum(int[] array, int left,int right){
int mid = (left+right)/2;
//求中位數(shù)的下標(biāo)
if(array[left] < array[right]){
if(array[mid]<array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
//array[left] > array[right]
if(array[mid]>array[left]){
return left;
}else if(array[mid] < array[right]){
return right;
}else{
return mid;
}
}
}
public static void insertSort(int[] array, int left,int right) {
for (int i = left+1; i <= right; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= left; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
private static void quick2(int[] array, int start, int end){
if(start>=end){
return;
}
if(end-start+1<=15){
insertSort(array,start,end);
return;
}
//1 2 3 4 5 6 7
int index = middleNum(array,start,end);
swap(array,index,start);
//4 2 3 1 5 6 7
int pivot = partition(array,start,end);
quick2(array,start,pivot-1);
quick2(array,pivot+1,end);
}非遞歸快排
先利用挖坑法排好序
創(chuàng)建一個(gè)棧，把6左邊第一個(gè)和最后一個(gè)元素(pivot-1)的位置放入棧中，右邊同理
彈出一個(gè)9給r，彈出6給l
?再重復(fù)一次挖坑法partition方法
9右邊的元素不需要遞歸，所以直接當(dāng)成pivot?
把9左邊的第一個(gè)元素下標(biāo)(6)和最后一個(gè)元素(7)放入棧中
?
怎么判斷pivot左邊和右邊有多少個(gè)元素呢？
當(dāng)pivot+1 = e的時(shí)候，右邊只有1個(gè)元素；當(dāng)pivot+1<e的時(shí)候，右邊有兩個(gè)或兩個(gè)以上的元素
相反當(dāng)pivot-1>s，左邊有兩個(gè)或兩個(gè)以上元素
總結(jié)步驟：
1.調(diào)用partition方法找出整個(gè)數(shù)組的中間數(shù)位置pivot
2.左邊有沒(méi)有兩個(gè)元素，下標(biāo)放到棧
3.右邊一樣
4.判斷?？詹豢?->不空的話(huà)就pop兩個(gè)元素出來(lái)分別交給r和l（注意最先出來(lái)的給r，慢一點(diǎn)的給l）
整個(gè)代碼：
public static void quickSortNor(int[] array){
int start = 0;
int end = array.length-1;
Stack<Integer> stack = new Stack<>();
int pivot = partitionHoare(array,start,end);
if(pivot>start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot+1<end){
stack.push(pivot+1);
stack.push(end);
}
while(!stack.isEmpty()){
end = stack.pop();
start=stack.pop();
pivot = partitionHoare(array,start,end);
if(pivot>start+1){
stack.push(start);
stack.push(pivot-1);
}
if(pivot+1<end){
stack.push(pivot+1);
stack.push(end);
}
}
}歸并排序
分治算法+二路歸并
分解：
public static void mergeSort(int[] array){
mergeSortFun(array,0, array.length-1);
}
private static void mergeSortFun(int[] array,int start,int end){
if(start>=end){
return;
}
//分解
int mid = (start+end)/2;
mergeSortFun(array,start,mid);
mergeSortFun(array,mid+1,end);
//合并
merge(array,start,mid,end);
}歸并方法
創(chuàng)建一個(gè)tmpArr數(shù)組記錄排序好的數(shù)字
先進(jìn)行s1和s2兩個(gè)元素的比較，s2的元素比較小先扔到tmpArr里面，s2++
?接著再比較s2和s1，發(fā)現(xiàn)s1更小，扔到tmpArr里面，s1++
后面的步驟差不多，比較s1和s2兩個(gè)元素，誰(shuí)小誰(shuí)放進(jìn)數(shù)組
private static void merge(int[] array, int left, int mid,int right) {
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int[] tmpArr = new int[right-left+1];
int k = 0;//tmpArr的下標(biāo)
//同時(shí)滿(mǎn)足兩個(gè)歸并段都有數(shù)據(jù)
while(s1 <= e1 && s2 <= e2){
if(array[s1] <= array[s2]){
tmpArr[k++] = array[s1++];
}else{
tmpArr[k++] = array[s2++];
}
}
while(s1 <= e1){
tmpArr[k++] = array[s1++];
}
while(s2 <= e2){
tmpArr[k++] = array[s2++];
}
//把排好的數(shù)據(jù)拷貝回原來(lái)的數(shù)組array中
for (int i = 0; i < tmpArr.length; i++) {
array[i+left] = tmpArr[i];
}
}時(shí)間復(fù)雜度
每次都要遍歷n個(gè)元素，而分解過(guò)程分治算法和二路歸并的復(fù)雜度logn
總的復(fù)雜度O(N*logN)
穩(wěn)定性：穩(wěn)定
非遞歸歸并
先讓每組的兩個(gè)數(shù)據(jù)進(jìn)行排序，接著再讓兩個(gè)組的四個(gè)數(shù)據(jù)進(jìn)行排序
每組一個(gè)數(shù)據(jù)進(jìn)行排序
兩組的數(shù)據(jù)排序
?
int gap = 1;
while(gap<array.length){
for (int i = 0; i < array.length; i = i+gap*2) {
int left = i;
int mid = left+gap-1;
int right = mid+gap;
merge(array,left,mid,right);
}
gap*=2;
}mid和right的定義方式可能會(huì)有越界的風(fēng)險(xiǎn)
所以我們需要進(jìn)行風(fēng)險(xiǎn)修正
if(mid >= array.length){
mid = array.length-1;
}
if(right>=array.length){
right = array.length-1;
}整個(gè)代碼：
public static void mergeSortNor(int[] array){
int gap = 1;
while(gap<array.length){
for (int i = 0; i < array.length; i = i+gap*2) {
int left = i;
int mid = left+gap-1;
int right = mid+gap;
if(mid >= array.length){
mid = array.length-1;
}
if(right>=array.length){
right = array.length-1;
}
merge(array,left,mid,right);
}
gap*=2;
}
}應(yīng)用
1.先把文件切割成200份，每個(gè)512M
2.分別對(duì)512M排序，任意排序都行，因?yàn)閮?nèi)存放的下
3.進(jìn)行2路歸并，同時(shí)對(duì)200份有序文件做歸并過(guò)程，最終結(jié)果就是有序了
排序總結(jié)
其他排序
計(jì)數(shù)排序
簡(jiǎn)單版本
有這么一組數(shù)字，要求你進(jìn)行排序，注意這組數(shù)組在0~9之間
1.先申請(qǐng)一個(gè)計(jì)數(shù)數(shù)組count，設(shè)置一個(gè)i，定義co把每個(gè)數(shù)字出現(xiàn)的次數(shù)記錄下來(lái)。i遍歷上面的數(shù)字，每次遍歷到重復(fù)的數(shù)字就co++(count[array[i] - minVal]++)
?計(jì)數(shù)數(shù)組上面的數(shù)字代表數(shù)組里面出現(xiàn)的數(shù)字，不是下標(biāo)
如果不一定是以0為最小值的呢？
那我們就需要定義數(shù)組最小值minVal和最大值maxVal了
int minVal = array[0];
int maxVal = array[0];
for (int i = 0; i < array.length; i++) {
if(array[i]<minVal){
minVal = array[i];
}
if(array[i]>maxVal){
maxVal=array[i];
}
}數(shù)組長(zhǎng)度？
//確定計(jì)數(shù)數(shù)組的長(zhǎng)度
int len = maxVal-minVal+1;
int[] count = new int[len]; //遍歷array數(shù)組 把數(shù)據(jù)出現(xiàn)的次數(shù)存儲(chǔ)到計(jì)數(shù)數(shù)組中
for (int i = 0; i < array.length; i++) {
count[array[i]-minVal]++;
}2.設(shè)置一個(gè)i遍歷這個(gè)計(jì)數(shù)數(shù)組，把每個(gè)數(shù)字重復(fù)（如果有）記錄下來(lái)并寫(xiě)回原來(lái)的數(shù)組
?
//遍歷計(jì)數(shù)數(shù)組，把實(shí)際的數(shù)組寫(xiě)回array數(shù)組
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i]>0){
//這里需要寫(xiě)回array,得從array的0位置開(kāi)始寫(xiě)
array[index] = i+minVal;
index++;
//每次寫(xiě)進(jìn)array一個(gè)元素，計(jì)數(shù)數(shù)組的對(duì)應(yīng)元素?cái)?shù)量就得減少
count[i]--;
}
}整個(gè)代碼：
public static void countSort(int[] array){
//求數(shù)組最大值和最小值 O(N)
int minVal = array[0];
int maxVal = array[0];
for (int i = 0; i < array.length; i++) {
if(array[i]<minVal){
minVal = array[i];
}
if(array[i]>maxVal){
maxVal=array[i];
}
}
//確定計(jì)數(shù)數(shù)組的長(zhǎng)度
int len = maxVal-minVal+1;
int[] count = new int[len];
//遍歷array數(shù)組 把數(shù)據(jù)出現(xiàn)的次數(shù)存儲(chǔ)到計(jì)數(shù)數(shù)組中 O(N)
for (int i = 0; i < array.length; i++) {
count[array[i]-minVal]++;
}
//遍歷計(jì)數(shù)數(shù)組，把實(shí)際的數(shù)組寫(xiě)回array數(shù)組
//跟最大值和最小值有關(guān)系，所以是O(范圍)
int index = 0;
for (int i = 0; i < count.length; i++) {
while(count[i]>0){
//這里需要寫(xiě)回array,得從array的0位置開(kāi)始寫(xiě)
array[index] = i+minVal;
index++;
//每次寫(xiě)進(jìn)array一個(gè)元素，計(jì)數(shù)數(shù)組的對(duì)應(yīng)元素?cái)?shù)量就得減少
count[i]--;
}
}
}時(shí)間復(fù)雜度：O(MAX(N, 范圍))
空間復(fù)雜度：O(范圍)
穩(wěn)定性：不穩(wěn)定
復(fù)雜版本（穩(wěn)定版本）
這里字?jǐn)?shù)太多（主要是我懶~），大家可以去看這篇博客計(jì)數(shù)排序 - 知乎 (zhihu.com)
基數(shù)排序?
基數(shù)排序動(dòng)圖演示
從低位到高位數(shù)字，讓每位數(shù)字依次有序
代碼見(jiàn)下：
1.10 基數(shù)排序 | 菜鳥(niǎo)教程 (runoob.com)?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-741090.html
桶排序?
【排序】圖解桶排序_桶排序圖解-CSDN博客文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-741090.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：排序干貨?。?大排序匯總+快速排序的優(yōu)化+計(jì)數(shù)排序+基數(shù)排序+桶排序）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
