排序
分析排序算法
执行效率
1. 最好、最坏、平均时间复杂度
数据的有序程度不一样，对排序算法时间复杂度的影响很大，所以需要对最好、最坏情况复杂度有了解
2. 时间复杂度的系数、常数
当两个算法的时间复杂度是一个阶层的，这时就需要考虑它们的系数或者常数项，以此来判断快慢
3. 比较次数和交换次数
基于比较的排序算法基本都有比较和交换的操作，计算时间复杂度的时候，需要把这两种操作计算进去
内存消耗
内存消耗可以用空间复杂度来表示，对于空间复杂度为 O(1) 排序算法，称其为 原地排序
稳定性
针对排序算法，还有另外一个指标，即算法的稳定性。
算法的稳定性指的是，排序关键字相同的两个项，在排序之前和之后的相对位置是否变化，若相对位置没有变化，则是稳定排序算法，否则是非稳定排序算法
O(n2) 复杂度排序算法
| 算法 | 原地排序 | 稳定排序 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 |
|---|---|---|---|---|---|
| 冒泡排序 | 是 | 是 | O(n) - 数组有序 | O(n2) - 数组逆序 | O(n2) |
| 插入排序 | 是 | 是 | O(n) - 数组有序 | O(n2) - 数组逆序 | O(n2) |
| 选择排序 | 是 | 否 | O(n2) | O(n2) | O(n2) |
1. 冒泡排序
思想：每次比较相邻的两个数，满足交换条件则交换两个数，所以每次都能将未排序的最大(小)的数冒泡到末尾，循环 n 次后，数组已经有序
可优化点：当某次冒泡中没有发生数据交换时，此时数组已经有序，不需要再进行后续的冒泡比较了
function quickSort(arr) {
if(!arr || arr.length < 2) {
return arr;
}
for (let i = 0; i < arr.length; i++) {
// j 和 j + 1 比较，最后一个元素就是 j + 1，所以 - 1
const top = arr.length - i - 1;
let isSorted = true;
for(let j = 0; j < top; j++) {
if (arr[j] > arr[j+1]) {
const temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
return arr;
}
2. 插入排序
思想： 将数组分为 已排序区间和未排序区间，每次从将未排序区间第一个元素插入到已排序区间的正确位置上
// 使用 js 数组方法
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
const ordered = arr.slice(0, i);
const value = arr[i];
const index = ordered.findIndex(val => val > value);
if (index !== -1) {
arr.splice(i, 1);
arr.splice(index, 0, value);
}
}
return arr;
}
// 不使用 js 数组方法
function insertSort(arr) {
if (arr.length < 2) {
return arr;
}
for (let i = 1; i < arr.length; i++) {
const value = arr[i];
let j = i;
while (j--) {
if (arr[j] > value) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = value;
}
return arr;
}
3. 选择排序
思想： 也是将数组分为 已排序区间和未排序区间，每次从未排序区间中找到最小值，和未排序区间第一个值做交换
function selectSort(arr) {
if (arr.length < 1) {
return arr;
}
let orderedTrail = 0;
while (orderedTrail < arr.length){
let j = orderedTrail;
let min = arr[j];
let minIndex = j;
while (j < arr.length) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
j += 1;
}
arr[minIndex] = arr[orderedTrail];
arr[orderedTrail++] = min;
}
return arr;
}
O(nlogn) 复杂度排序算法
| 算法 | 原地排序 | 稳定排序 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 |
|---|---|---|---|---|---|
| 归并排序 | 否 - O(n) | 是 | O(nlogn) | O(nlogn) | O(nlogn) |
| 快速排序 | 是 | 否 | O(O(nlogn)) - 分区比较均衡 | O(n2) - 分区及其不均衡 | O(O(nlogn)) |
1. 归并排序
思想： 把数组分为前后两个部分，分别对两个部分进行排序，然后将排好序的两部分合并，则数组有序( 分而治之的思想 )
function mergeSort(arr) {
if (!arr || !Array.isArray(arr) || !arr.length) {
return [];
}
const merge = function(left, middle, right) {
const tempArr = Array(right - left);
let index = 0;
let leftIndex = left;
let rightIndex = middle;
while (leftIndex < middle && rightIndex < right) {
const leftValue = arr[leftIndex];
const rightValue = arr[rightIndex];
if (leftValue <= rightValue) {
tempArr[index++] = leftValue;
leftIndex += 1;
} else {
tempArr[index++] = rightValue;
rightIndex += 1;
}
}
let start = leftIndex < middle ? leftIndex : rightIndex;
let end = leftIndex < middle ? middle : right;
while (start < end) {
tempArr[index++] = arr[start++];
}
end = right - left;
for (start = 0; start < end; start++) {
arr[start + left] = tempArr[start];
}
}
const sort = function(left, right) {
if (left >= right) {
return;
}
const middle = ((right + left) / 2) >> 0;
sort(left, middle);
sort(middle + 1, right);
merge(left, middle, right);
}
sort(0, arr.length)
return arr;
}
时间复杂度分析： T(n) = T(n/2)(左伴部分的时间复杂度) + T(n/2)(右半部分的时间复杂度) + K(合并时的时间复杂度)，可以以此推出 T(n) = 2^k*T(n/2^k) + k*n，当 2^k == 1时，k = logn，带入即可得 T(n) = nlogn + Cn
2. 快速排序
思想： 取区间任意位置为标准值，遍历区间，比标准值小的都放在左边，比标准值大的都放在右边，以此类推，直到只有一个元素，此时数组有序( 分而治之的思想 )
function quickSort(arr) {
if (!arr || !Array.isArray(arr) || !arr.length) {
return [];
}
const swap = function(i ,j) {
const temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
const partial = function(left, right) {
const reference = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < reference) {
swap(i, j)
i += 1;
}
}
swap(i, right);
return i;
}
const sort = function(left, right) {
if (left >= right) {
return;
}
border = partial(left, right);
sort(left, border - 1);
sort(border + 1, right);
}
sort(0, arr.length - 1);
return arr;
}
注意： 由于在交换元素的过程中可能会破坏数组项的原本的先后顺序，所以快速排序是非稳定排序
O(n) 复杂度排序算法
1. 桶排序
思想： 根据数据范围，分几个桶，将对应区间的数据放到对应的桶中进行排序，然后根据桶的顺序合并每个桶中的数据
桶排序
复杂度分析： 当划分为 m个桶时，如果划分均匀，则每个桶有 k = n/m 个项，若对每个桶采用快速排序，则复杂度为 O(k*logk)，m 个桶的总复杂度为 O(m*k*logk)，又有 k = n/m，则为 O(n*log(n/m))，可见，当桶的个数越接近项的个数，时间复杂度越接近 O(n)
2. 基数排序
思想： 根据数据的每一位分别进行排序，需要使用稳定的排序算法
