常見的八種排序算法
排序算法結(jié)構(gòu)圖
各種排序算法的比較
不穩(wěn)定：快選堆希
穩(wěn) 定：插冒歸基
直接插入排序：
算法思想：
將數(shù)組中所有的元素與前面已經(jīng)排好序的元素進(jìn)行比較，如果選擇的元素比已排序的元素小割粮，則交換
使用兩個循環(huán)完成：
第一層循環(huán)：遍歷待比較的所有元素
第二層循環(huán)：將本輪選擇的元素與已經(jīng)排好序的元素相比較，如果選擇的元素比已排序的元素小，則交換
- 時間復(fù)雜度：
平均情況：O(n2)
最好情況：O(n) 已排好序的數(shù)列
最壞情況：O(n2) 逆序的數(shù)列 - 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
for (var i = 0; i < arr.length; i++) {
for (var j = i; j > -1; j-- ) {
if (arr[j] < arr[j - 1]) {
var t = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = t;
}
}
}
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
希爾排序
算法思想：
將數(shù)組按下標(biāo)進(jìn)行一定增量的分組拳球，對每組使用插入算法排序，隨著增量的減少珍特，每組包含的數(shù)據(jù)會越來越多祝峻，當(dāng)增量為1時，整個數(shù)組都被分到一組，算法即終止莱找。
- gap（增量）：length / 2 酬姆，而后依次以gap = gap / 2，所以增量序列為{length / 2, (length / 2) / 2, ..., 1}
注意： 希爾排序的增量序列的選擇與證明是個數(shù)學(xué)難題奥溺，我們選擇的這個增量序列是比較常用的辞色，也是希爾建議的增量，稱為希爾增量浮定，但其實(shí)這個增量序列不是最優(yōu)的相满。此處我們做示例使用希爾增量。 - 時間復(fù)雜度：
平均情況：O(n2)
最好情況：O(n)
最壞情況：O(n2) - 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
for (var gap = Math.floor(arr.length / 2); gap >= 1; gap = Math.floor(gap / 2)) {
console.log('gap = ', gap); //gap = 4, gap = 2, gap = 1
for (var i = gap; i < arr.length; i++) {
for (var j = i; j >= 0; j -= gap) {
if (arr[j] < arr[j - gap]) {
var t = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = t;
}
}
}
}
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
簡單排序
算法思想：
- 從待排序的序列中桦卒，找到最小的元素立美；
- 如果最小元素不是第一個，將把最小元素與第一個交換方灾，將余下的元素置為待排序元素建蹄，重復(fù)1,2步驟，直到待排序元素為1裕偿。
- 時間復(fù)雜度：
平均情況：O(n2)
最好情況：O(n2)
最壞情況：O(n2) - 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
for (var i = 0; i < arr.length; i++) {
for (var j = i; j < arr.length; j++) {
if (arr[j] < arr[i]) {
var t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
}
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 8, 7, 9 ]
堆排序
算法思想：
- 將待排序序列構(gòu)造成一個大頂堆（小頂堆）洞慎，堆頂?shù)母?jié)點(diǎn)就是整個序列最大值（最小值）；
- 然后將其與末尾元素進(jìn)行交換击费，此時末尾元素就是最大值（最小值）了拢蛋；
- 將剩余的元素構(gòu)造成一個堆，重復(fù)1,2,3步驟蔫巩，直到剩余的元素為1谆棱。
注：
堆：堆是滿足大頂堆或小頂堆的完全二叉樹
大頂堆：每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值
小頂堆：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值
- 時間復(fù)雜度：
平均情況：O(nlog2n)
最好情況：O(nlog2n)
最壞情況：O(nlog2n) - 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
function ajustArr(arr, i, length) {
for (var j = i * 2 + 1; j < length; j = j * 2 + 1) {
if ((j + 1 < length) && (arr[j] < arr[j + 1])) {
j++;
}
if (arr[j] > arr[i]) {
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i = j;
}
}
}
function makeHeap(arr, n) {
for (var i = Math.floor(n / 2 - 1); i >= 0; i--) {
ajustArr(arr, i, n);
}
}
function heapSort(arr) {
makeHeap(arr, arr.length);
for (var i = arr.length - 1; i >= 0; i--) {
console.log(arr);
// [ 9, 8, 6, 7, 5, 1, 4, 2, 3 ]
// [ 8, 7, 6, 3, 5, 1, 4, 2, 9 ]
// [ 7, 5, 6, 3, 2, 1, 4, 8, 9 ]
// [ 6, 5, 4, 3, 2, 1, 7, 8, 9 ]
// [ 5, 3, 4, 1, 2, 6, 7, 8, 9 ]
// [ 4, 3, 2, 1, 5, 6, 7, 8, 9 ]
// [ 3, 1, 2, 4, 5, 6, 7, 8, 9 ]
// [ 2, 1, 3, 4, 5, 6, 7, 8, 9 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
var t = arr[i];
arr[i] = arr[0];
arr[0] = t;
ajustArr(arr, 0, i);
}
}
heapSort(arr);
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
冒泡排序
算法思想：
- 將序列中的左右元素進(jìn)行比較，保證右邊的元素始終大于（小于）左邊的元素圆仔；
- 循環(huán)執(zhí)行步驟1垃瞧，執(zhí)行完成后，序列的最后一個元素即為當(dāng)前序列的最大值（最小值）坪郭；
- 對剩余的元素循環(huán)執(zhí)行步驟1,2个从，直到剩余的元素為1。
- 時間復(fù)雜度：
平均情況：O(n2)
最好情況：O(n)
最壞情況：O(n2) - 空間復(fù)雜度：O(1)
- 穩(wěn)定性：穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
for (var i = 0; i < arr.length; i++) {
for (var j = i; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
var t = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = t;
}
}
}
console.log(arr); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
快速排序 （分治）
算法思想：
- 在列表中選擇一個基準(zhǔn)數(shù)（pivot）
- 將序列當(dāng)中的所有數(shù)依次遍歷歪沃，比基準(zhǔn)數(shù)大的位于其右側(cè)嗦锐，比基準(zhǔn)數(shù)小的位于其左側(cè)
- 重復(fù)步驟1,2，直到所有子集當(dāng)中只有一個元素為止沪曙。
- 時間復(fù)雜度：
平均情況：O(nlog2n)
最好情況：O(nlog2n)
最壞情況：O(n2) - 空間復(fù)雜度：O(nlog2n)
- 穩(wěn)定性：不穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
function quickSort(arr, start, end) {
if (start < end) {
var pivot = arr[start];
var left = start;
var right = end;
while(left < right) {
while((left < right) && (pivot <= arr[right])) right--;
if (left < right) {
arr[left] = arr[right];
left++;
}
while((left < right) && (pivot >= arr[left])) left++;
if (left < right) {
arr[right] = arr[left];
right--;
}
}
arr[left] = pivot;
console.log(arr);
// [ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
// [ 1, 2, 3, 4, 5, 6, 9, 8, 7 ]
// [ 1, 2, 3, 4, 5, 6, 9, 8, 7 ]
// [ 1, 2, 3, 4, 5, 6, 9, 8, 7 ]
// [ 1, 2, 3, 4, 5, 6, 9, 8, 7 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
quickSort(arr, left + 1, end);
quickSort(arr, start, left - 1);
}
}
quickSort(arr, 0, arr.length - 1);
console.log(arr); //[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
歸并排序（分治）
建立在歸并操作上的排序算法奕污，是分治法的典型應(yīng)用。
算法思想：
將數(shù)據(jù)分為兩組液走，如果組內(nèi)數(shù)據(jù)只有一個時碳默，認(rèn)為組內(nèi)數(shù)據(jù)有序贾陷，然后進(jìn)行合并相鄰的兩組數(shù)據(jù)即可
如何將兩個有序數(shù)列合并？
比較兩個數(shù)列的第一個數(shù)嘱根，誰小就先取誰髓废，取了后就在對應(yīng)數(shù)列中刪除這個數(shù)，然后再進(jìn)行比較该抒，如果數(shù)列為空慌洪，那就直接將另一個數(shù)列的數(shù)據(jù)依次取出。時間復(fù)雜度：
平均情況：O(nlog2n)
最好情況：O(nlog2n)
最壞情況：O(nlog2n)空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定
var arr = [1, 3, 4, 2, 5, 6, 9, 8, 7];
console.log(arr); //[ 1, 3, 4, 2, 5, 6, 9, 8, 7 ]
function mergeArr(arr, start, mid, end) {
var tem = [], k = 0, i = start, j = mid + 1;
while((i <= mid) && (j <= end)) {
if (arr[i] <= arr[j]) {
tem[k++] = arr[i++];
} else {
tem[k++] = arr[j++];
}
}
while(i <= mid) {
tem[k++] = arr[i++];
}
while(j <= end) {
tem[k++] = arr[j++];
}
console.log('tem:', tem);
// tem: [ 1, 3 ]
// tem: [ 1, 3, 4 ]
// tem: [ 2, 5 ]
// tem: [ 1, 2, 3, 4, 5 ]
// tem: [ 6, 9 ]
// tem: [ 7, 8 ]
// tem: [ 6, 7, 8, 9 ]
// tem: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
for (var i = 0; i < k; i++) {
arr[start + i] = tem[i];
}
}
function mergeSort(arr, start, end) {
if (start < end) {
var mid = Math.floor((start + end) / 2);
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
mergeArr(arr, start, mid, end);
}
}
mergeSort(arr, 0, arr.length - 1);
console.log(arr); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
