排序算法
文章目录

TLDR: 常见算法

  • 冒泡排序
  • 计数排序
  • 快速排序
  • 归并排序
  • 插入排序
  • 选择排序

算法分类

  • 比较类排序: 通过比较来决定元素间的相对次序, 由于其时间复杂度不能突破 O(nlogn), 因此也称为非线性时间比较类排序.
    • 交换排序
      • 冒泡排序
      • 快速排序
    • 插入排序
      • 简单插入排序
      • 希尔排序
    • 选择排序
      • 简单选择排序
      • 堆排序
    • 归并排序
  • 非比较类排序: 不通过比较来决定元素间的相对次序, 它可以突破基于比较排序的时间下界, 以线性时间运行, 因此也称为线性时间非比较类排序.
    • 基数排序
    • 计数排序
    • 桶排序

算法详细

冒泡排序

  • 比较相邻的元素. 如果第一个比第二个大, 就交换它们两个。
  • 每次循环后最后一个是最大的, 固定不动
  • 重复操作剩余元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(arr) {
varlen = arr.length;
for (vari = 0; i < len - 1; i++) {
for (varj = 0; j < len - 1 - i; j++) {
// 相邻元素两两对比
if (arr[j] > arr[j + 1]) {
// 两个元素交换位置
vartemp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}

选择排序

  • 每次扫描一边数组取出最小的放到另一个数组末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
varlen = arr.length;
varminIndex, temp;
for(vari = 0; i < len - 1; i++) {
minIndex = i;
for(varj = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}

插入排序

  • 每次取后面一个元素, 然后和之前已排序的元素进行比较插入到之前已排序的数组当中.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
varlen = arr.length;
varpreIndex, current;
for(vari = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

快速排序

  • 从数列中挑出一个元素, 称为 “基准”(pivot) ;
  • 重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面 (相同的数可以到任一边) . 在这个分区退出之后, 该基准就处于数列的中间位置. 这个称为分区 (partition) 操作;
  • 递归地 (recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function quickSort(arr, left, right) {
varlen = arr.length,
partitionIndex,
left =typeofleft !='number'? 0 : left,
right =typeofright !='number'? len - 1 : right;

if(left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}

function partition(arr, left ,right) { // 分区操作
varpivot = left, // 设定基准值(pivot)
index = pivot + 1;
for(vari = index; i <= right; i++) {
if(arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}

function swap(arr, i, j) {
vartemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

计数排序

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为 i 的元素出现的次数, 存入数组 C 的第 i 项;
  • 对所有的计数累加 (从 C 中的第一个元素开始, 每一项和前一项相加) ;
  • 反向填充目标数组: 将每个元素 i 放在新数组的第 C(i) 项, 每放一个元素就将 C(i) 减去 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countingSort(arr, maxValue) {
varbucket =newArray(maxValue + 1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;

for(vari = 0; i < arrLen; i++) {
if(!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}

for(varj = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}

return arr;
}

归并排序

  • 把长度为 n 的输入序列分成两个长度为 n/2 的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function mergeSort(arr) {
varlen = arr.length;
if(len < 2) {
returnarr;
}
varmiddle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
returnmerge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
varresult = [];

while(left.length>0 && right.length>0) {
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());

return result;
}