排序
2018-10-29 本文已影响0人
楼下的黑猫不太冷
常见的八种排序算法
排序算法结构图
各种排序算法的比较
不稳定：快选堆希
稳 定：插冒归基
直接插入排序：
算法思想：
将数组中所有的元素与前面已经排好序的元素进行比较，如果选择的元素比已排序的元素小，则交换
使用两个循环完成：
第一层循环：遍历待比较的所有元素
第二层循环：将本轮选择的元素与已经排好序的元素相比较，如果选择的元素比已排序的元素小，则交换
- 时间复杂度：
平均情况：O(n2)
最好情况：O(n) 已排好序的数列
最坏情况：O(n2) 逆序的数列 - 空间复杂度：O(1)
- 稳定性：稳定
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 ]
希尔排序
算法思想：
将数组按下标进行一定增量的分组，对每组使用插入算法排序，随着增量的减少，每组包含的数据会越来越多，当增量为1时，整个数组都被分到一组，算法即终止。
- gap（增量）：length / 2 ，而后依次以gap = gap / 2，所以增量序列为{length / 2, (length / 2) / 2, ..., 1}
注意： 希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。 - 时间复杂度：
平均情况：O(n2)
最好情况：O(n)
最坏情况：O(n2) - 空间复杂度：O(1)
- 稳定性：不稳定
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 ]
简单排序
算法思想：
- 从待排序的序列中，找到最小的元素；
- 如果最小元素不是第一个，将把最小元素与第一个交换，将余下的元素置为待排序元素，重复1,2步骤，直到待排序元素为1。
- 时间复杂度：
平均情况：O(n2)
最好情况：O(n2)
最坏情况：O(n2) - 空间复杂度：O(1)
- 稳定性：不稳定
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 ]
堆排序
算法思想：
- 将待排序序列构造成一个大顶堆（小顶堆），堆顶的根节点就是整个序列最大值（最小值）；
- 然后将其与末尾元素进行交换，此时末尾元素就是最大值（最小值）了；
- 将剩余的元素构造成一个堆，重复1,2,3步骤，直到剩余的元素为1。
注：
堆：堆是满足大顶堆或小顶堆的完全二叉树
大顶堆：每个结点的值都大于或等于其左右孩子结点的值
小顶堆：每个结点的值都小于或等于其左右孩子结点的值
- 时间复杂度：
平均情况：O(nlog2n)
最好情况：O(nlog2n)
最坏情况：O(nlog2n) - 空间复杂度：O(1)
- 稳定性：不稳定
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 ]
冒泡排序
算法思想：
- 将序列中的左右元素进行比较，保证右边的元素始终大于（小于）左边的元素；
- 循环执行步骤1，执行完成后，序列的最后一个元素即为当前序列的最大值（最小值）；
- 对剩余的元素循环执行步骤1,2，直到剩余的元素为1。
- 时间复杂度：
平均情况：O(n2)
最好情况：O(n)
最坏情况：O(n2) - 空间复杂度：O(1)
- 稳定性：稳定
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 ]
快速排序 （分治）
算法思想：
- 在列表中选择一个基准数（pivot）
- 将序列当中的所有数依次遍历，比基准数大的位于其右侧，比基准数小的位于其左侧
- 重复步骤1,2，直到所有子集当中只有一个元素为止。
- 时间复杂度：
平均情况：O(nlog2n)
最好情况：O(nlog2n)
最坏情况：O(n2) - 空间复杂度：O(nlog2n)
- 稳定性：不稳定
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 ]
归并排序（分治）
建立在归并操作上的排序算法，是分治法的典型应用。
算法思想：
将数据分为两组，如果组内数据只有一个时，认为组内数据有序，然后进行合并相邻的两组数据即可
-
如何将两个有序数列合并？
比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数，然后再进行比较，如果数列为空，那就直接将另一个数列的数据依次取出。 -
时间复杂度：
平均情况：O(nlog2n)
最好情况：O(nlog2n)
最坏情况：O(nlog2n) -
空间复杂度：O(1)
-
稳定性：稳定
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 ]
