1. 排序的概念
排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性：假設(shè)在待排序的序列中，存在多個(gè)具有相同內(nèi)容的元素，如果經(jīng)過排序，這些元素的相對(duì)位置并不發(fā)生改變，則稱這種排序算法是穩(wěn)定的。
穩(wěn)定的排序可以變成不穩(wěn)定的，但是不穩(wěn)定的排序算法是不可能變成穩(wěn)定的。
例如：
排序前：4a 6 5 9 3 4b 7 2
排序后：2 3 4a 4b 5 6 7 9 ==》穩(wěn)定
排序后：2 3 4b 4a 5 6 7 9 ==》不穩(wěn)定
穩(wěn)定性存在的意義是什么？
比如說：小明用半小時(shí)交卷得了一百分，小剛用一小時(shí)交卷得了一百分，最終以分?jǐn)?shù)排名的時(shí)候，第一名一定是小明，不可能是小剛，因?yàn)樾∶鞅刃傁冉痪怼?/p>
穩(wěn)定性好的排序就會(huì)把小明放在第一名，而穩(wěn)定性差的排序可能會(huì)把小剛放在第一名，對(duì)小明不公平。
這樣穩(wěn)定性的意義就體現(xiàn)出來了。
內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序：數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
2. 常見的排序算法
3. 排序算法的實(shí)現(xiàn)
3.1 插入排序
插入排序的中心思想就是：將待排序的元素按照自身大小逐個(gè)插入到已經(jīng)排好序的有序序列中，直到所有的元素插完為止。
3.1.1 直接插入排序
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移。
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int n = array[i];//當(dāng)前待排序元素
int j = i - 1;
for (; j >= 0; j--) {
//待排序的元素與前面排好序的元素進(jìn)行比較
if(n < array[j]) {
//當(dāng)前待排序元素<排好序的元素
array[j + 1] = array[j];
//排好序的元素后移
} else {
//當(dāng)前待排序元素>=排好序的元素，證明此時(shí)待排序元素找到了自己的位置，中斷比較
break;
}
}
array[j + 1] = n;//將待排序的元素放在自己的位置。
//為什么是將待排序的元素賦值給array[j + 1]呢？
//因?yàn)閍rray[j + 1] > n > array[j] ,array[j + 1] 的值已經(jīng)賦給后一個(gè)元素了，所以將待排序的元素賦值給array[j + 1]
}
}
測(cè)試10_0000個(gè)數(shù)據(jù)排序所用時(shí)間（單位：ms）
特點(diǎn)：
- 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高。
- 時(shí)間復(fù)雜度：最壞的情況下（逆序）O(N2)， 最好的情況下（正序）O(N);
- 數(shù)據(jù)越有序的時(shí)候，排序越快
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
3.1.2 希爾排序（縮小增量排序）
希爾排序的中心思想是：
先選定一個(gè)整數(shù)，把待排序元素分成多個(gè)組，將所有距離為n的元素分到一組內(nèi)，然后對(duì)每一組內(nèi)的元素進(jìn)行排序，然后取n的一半或者其他小于n的整數(shù)，重復(fù)上述工作。當(dāng)n = 1時(shí)，所有的元素在統(tǒng)一組內(nèi)排好序。
簡單來說，就分為兩步：
-
分組->縮小增量
這里的分組并不是將連續(xù)的元素分在一組內(nèi)，而是跳躍式分組，這樣可以盡量把大的數(shù)據(jù)放到后面，把小的數(shù)據(jù)放到前面
-
組內(nèi)進(jìn)行插入排序
組內(nèi)的每一次排序都是插入排序
gap的取法有很多種：可以是gap = n / 2，gap = gap / 2；也可以是gap = gap / 3 + 1；還有人說都取奇數(shù)為好；也有人提出gap互質(zhì)為好。但是無論哪一種都沒有得到證明。
我用的是gap = n / 2，gap = gap / 2這種取法。
下面是大體步驟：
public static void shell(int[] arr, int gap) {
for(int i = gap; i < arr.length; i++) {
//這里為什么是i++而不是i+=gap的原因：
//因?yàn)槿绻莍+=gap，i只會(huì)比較第一個(gè)組，因?yàn)榈谝粋€(gè)組比較完了之后，i > arr.length，不能進(jìn)入循環(huán)了。
//而如果是i++，那么i就會(huì)遍歷到每一個(gè)組，每一個(gè)成員，進(jìn)行插入排序。
int n = arr[i];
int j = i - gap;
for(; j >= 0; j-=gap) {
//這里j-=gap就能保證每個(gè)元素都在自己的組內(nèi)進(jìn)行比較
if(arr[j] > n) {
arr[j + gap] = arr[j];
} else {
break;
}
}
arr[j + gap] = n;
}
}
public static void shellSort(int[] arr) {
int gap = arr.length;
while(gap > 1) {
gap /= 2;
shell(arr, gap);
}
}
特點(diǎn)
- 希爾排序是對(duì)直接插入排序的優(yōu)化
- 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近于有序了，這樣就會(huì)很快。
- 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)樗倪\(yùn)行時(shí)間依賴于gap的選擇，導(dǎo)致很難去計(jì)算，是一個(gè)長期未解決的問題。在很多書中給出的時(shí)間復(fù)雜度都不固定。大約是在n1.25 到1.6*n1.25 范圍內(nèi)
- 不穩(wěn)定
3.2 選擇排序
3.2.1 基本思想
每一次從待排序的數(shù)據(jù)元素中選出最小（大）的一個(gè)元素，存放在序列的起始位置，直到全部待排序的元素排完。
3.2.2 直接選擇排序
升序 ：在元素arr[i] – arr[n - 1]中選出最小的元素，與arr[i]進(jìn)行交換，i++，重復(fù)上述步驟，直到i遍歷到最后一個(gè)元素為止。
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int index = i;
for (int j = i + 1; j < arr.length; j++) {
if(arr[index] > arr[j]) {
//挑選最小元素，記錄位置
index = j;
}
}
swap(arr, i, index);
}
}
private static void swap(int[] arr, int index1, int index2) {
int n = arr[index1];
arr[index1] = arr[index2];
arr[index2] = n;
}
還有另一種做法，就是每次遍歷都會(huì)找出一個(gè)最大值和最小值，進(jìn)行兩次交換。兩種做法的時(shí)間復(fù)雜度是一樣的。
public static void selectSort0(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (right > left) {
int minIndex = left;
int maxIndex = left;
for(int i = left + 1; i <= right; i++) {
if(arr[i] < arr[minIndex]) {
minIndex = i;
}
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
swap(arr, minIndex, left);
//這里要特別注意一點(diǎn)：
//如果left這個(gè)下標(biāo)的值是最大值，left和minIndex換了之后，最大值的下標(biāo)就不是maxIndex了，最大值就被換到了minIndex了，所以這里要判斷一下。
if(maxIndex == left) {
maxIndex = minIndex;
}
swap(arr, maxIndex, right);
left++;
right--;
}
}
特點(diǎn):
- 直接選擇排序的思路好理解，但是效率比較低，不常用
- 時(shí)間復(fù)雜度：O(N2)，數(shù)組本身的序列對(duì)選擇排序的時(shí)間復(fù)雜度沒有影響。
- 空間復(fù)雜度：O(1)
- 不穩(wěn)定
可能會(huì)有人奇怪，逆序情況下，直接插入排序和選擇排序的時(shí)間復(fù)雜度都是O(N2)，為什么時(shí)間相差很多呢？
因?yàn)椴迦肱判蛟脚判蛟接行?，越有序就越快?/p>
注意：這里展現(xiàn)的時(shí)間只是感受一下排序之間的不同，僅供參考，每次運(yùn)行的結(jié)果都不一樣，并且數(shù)據(jù)量比較小，不能說明排序的時(shí)間復(fù)雜度！
3.2.3 堆排序
堆排序即利用堆的思想來進(jìn)行排序，總共分為兩個(gè)步驟：
- 建堆
- 升序：建大堆
- 降序：建小堆
-
利用堆刪除思想來進(jìn)行排序
按升序來舉例，升序要建大堆，為什么呢？因?yàn)榇蟾芽梢员ＷC堆頂元素是最大的，然后可以將堆頂元素和最后一個(gè)元素進(jìn)行交換，這樣就能確保最大的元素在最后面，然后再對(duì)0下標(biāo)這棵樹向下調(diào)整，以此類推，就可以得到一組有序的數(shù)據(jù)。
如圖所示：
建堆和堆刪除中都用到了向下調(diào)整，因此掌握了向下調(diào)整，就可以完成堆排序。
public static void heapSort(int[] arr) {
createBigHeat(arr);
int end = arr.length - 1;
while (end > 0) {
//讓堆頂元素與最后一個(gè)元素進(jìn)行交換，因?yàn)槎秧斣厥亲畲蟮脑?，將它放在最后一個(gè)，就讓最大的元素有序了
swap(arr, 0, end);
//只有0下標(biāo)這棵樹不符合大根堆，所以只需對(duì)0下標(biāo)這一顆樹進(jìn)行向下調(diào)整就行
siftDown(arr, 0, end);
end--;
}
}
private static void createBigHeat(int[] arr) {
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
}
private static void siftDown(int[] arr, int parent, int len) {
int child = parent * 2 + 1;
while(child < len) {
if(child + 1 < len && arr[child] < arr[child + 1]) {
child++;
}
if(arr[child] > arr[parent]) {
swap(arr, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
特點(diǎn)文章來源：http://www.zghlxwxcb.cn/news/detail-449077.html
- 因?yàn)槭褂昧硕?，比直接選擇排序效率高很多。
- 時(shí)間復(fù)雜度：O(
N*logN)，數(shù)組的初始順序?qū)Χ雅判虻膹?fù)雜度沒有影響。 - 空間復(fù)雜度：O(1)
- 不穩(wěn)定
更多關(guān)于堆的文章可以查看我的另一篇文章哦 -> 點(diǎn)擊這里
這篇文章先到這里，有什么疑問的，歡迎到評(píng)論區(qū)留言，我們下一篇文章再見~??
下篇預(yù)告：十大排序算法（中）：冒泡排序，快速排序（遞歸和非遞歸）、歸并排序（遞歸和非遞歸）文章來源地址http://www.zghlxwxcb.cn/news/detail-449077.html
到了這里，關(guān)于十大排序算法（上）直接插入排序、希爾排序、直接選擇排序、堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
