一、排序算法说明
- 排序的定义：对一序列对象根据某个关键字进行排序。
输入：n个数：a1,a2,a3,...,an 输出：n个数的排列:a1',a2',a3',...,an'，使得a1'<=a2'<=a3'<=...<=an' - 对于评述算法优劣术语的说明
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
- 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度: 一个算法执行所耗费的时间。
- 空间复杂度: 运行完一个程序所需内存的大小。
- 总结
-
对比
In-place: 占用常数内存，不占用额外内存 Out-place: 占用额外内存。
-
分类
二、详解
1.冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
- 算法描述
<1>.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
<2>.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
<3>.针对所有的元素重复以上的步骤，除了最后一个；
<4>.重复步骤1~3，直到排序完成。 - 算法实现
function bubbleSort(arr) {
let length = arr.length;
for(let i = 0;i < length-1;i++) {
for(let j = 0;j < length-1-i;j++) {
if(arr[j] > arr[j + 1]) { // 相邻元素对比
let temp = arr[j + 1]; // 交换位置
arr[j + 1] = arr[j];
arr[j] =temp;
}
}
}
return arr;
}
let arr = [2, 1, 19, 30, 27];
console.log(bubbleSort(arr))
- 算法分析
- 最佳情况
T(n) = O(n)（数据正序） - 最差情况
T(n) = O(n2)（数据反序） - 平均
T(n) = O(n2)
2.选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 算法描述
- <1>.初始状态：无序区为R[1..n]，有序区为空；
- <2>.第i趟排序(i=1,2,3...n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。排序开始时从无序区的第一个开始，对比后面的，如果遇到比这个小的，就记录下位置。该趟排序从当前无序区中选出最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- <3>.n-1趟结束，数组有序化了。
- 算法实现
function selectionSort(arr) {
let len = arr.length;
let minIndex, temp;
for(let i = 0;i < len;i++) {
minIndex = i;
for(let j = i + 1;j < len; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
console.timeEnd('选择排序耗时');
return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));
- 算法分析
- 最佳情况：T(n) = O(n2)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(n2)
3.插入排序（Insertion-Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
<1>.从第一个元素开始，该元素可以认为已经被排序；
<2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；
<3>.如果该元素（已排序）大于新元素，将该元素移到下一位置；
<4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
<5>.将新元素插入到该位置后；
<6>.重复步骤2~5。
算法实现
function insertionSort (array) {
if(Object.prototype.toString.call(array).slice(8, -1) == 'Array') {
console.time('插入排序耗时');
for (let i = 1;i < array.length; i++) {
let key = array[i];
let j = i - 1;
while(j >= 0 && array[j] > key) {
array[j + 1] = array[j]; //与前面排好序的对比
j--;
}
array[j + 1] = key; // 插入到最后对比的那个数后面
}
console.timeEnd('插入排序耗时：');
return array;
} else {
return 'array is not an Array!';
}
}
- 算法分析
- 最佳情况：输入数组按升序排列。T(n) = O(n)
- 最坏情况：输入数组按降序排列。T(n) = O(n2)
- 平均情况：T(n) = O(n2)
4.归并排序（Merge Sort）
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 算法描述
- <1>.把长度为n的输入序列分成两个长度为n/2的子序列；
- <2>.对这两个子序列分别采用归并排序；
- <3>.将两个排序好的子序列合并成一个最终的排序序列。
- 算法实现
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
console.time('归并排序耗时');
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
console.timeEnd('归并排序耗时');
return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
- 算法分析
- 最佳情况：T(n) = O(n)
- 最差情况：T(n) = O(nlogn)
- 平均情况：T(n) = O(nlogn)
5.快速排序（Quick Sort）
快速排序快，而且效率高！它是处理大数据最快的排序算法之一。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 算法描述
- <1>.从数列中挑出一个元素，称为 "基准"（pivot）；
- <2>.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- <3>.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 算法实现
let quickSort = function (arr) {
console.time('快速排序耗时');
if(arr.length <= 1) {return arr;}
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1) [0];
let left = [];
let right = [];
for (let i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
console.timeEnd('快速排序耗时');
return quickSort(left).concat([pivot], quickSort(right));
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr));
- 算法分析
- 最佳情况：T(n) = O(nlogn)
- 最差情况：T(n) = O(n2)
- 平均情况：T(n) = O(nlogn)
6.计数排序
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
- 算法描述
- <1>. 找出待排序的数组中最大和最小的元素；
- <2>. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- <3>. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- <4>. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
- 算法实现
function countingSort(array) {
var len = array.length,
B = [],
C = [],
min = max = array[0];
console.time('计数排序耗时');
for (var i = 0; i < len; i++) {
min = min <= array[i] ? min : array[i];
max = max >= array[i] ? max : array[i];
C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
}
for (var j = min; j < max; j++) {
C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
}
for (var k = len - 1; k >= 0; k--) {
B[C[array[k]] - 1] = array[k];
C[array[k]]--;
}
console.timeEnd('计数排序耗时');
return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr));
- 算法分析
- 最佳情况：T(n) = O(n+k)
- 最差情况：T(n) = O(n+k)
- 平均情况：T(n) = O(n+k)
