十大基本排序算法
排序算法可以分为内部排序和外部排序。
内部排序是数据记录在内存中进行排序。
而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
关于时间复杂度：
1.平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。
2.线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
3.O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序
4.线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。
关于稳定性：
1.稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。
2.不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。
1.冒泡排序
functionbubbleSort(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; } } } returnarr; }
2.选择排序
functionselectionSort(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; } returnarr;
3.插入排序
functioninsertionSort(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; } returnarr; }
4.希尔排序
functionshellSort(arr) { varlen=arr.length; for (vargap=Math.floor(len/2); gap>0; gap=Math.floor(gap/2)) { // 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行for (vari=gap; i<len; i++) { varj=i; varcurrent=arr[i]; while (j-gap>=0&¤t<arr[j-gap]) { arr[j] =arr[j-gap]; j=j-gap; } arr[j] =current; } } returnarr; }
5.归并排序
functionmergeSort(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)); } functionmerge(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()); returnresult; }
6.快速排序
functionquickSort(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); } returnarr; } functionpartition(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); returnindex-1; } functionswap(arr, i, j) { vartemp=arr[i]; arr[i] =arr[j]; arr[j] =temp; }
7.堆排序
varlen; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量functionbuildMaxHeap(arr) { // 建立大顶堆len=arr.length; for (vari=Math.floor(len/2); i>=0; i--) { heapify(arr, i); } } functionheapify(arr, i) { // 堆调整varleft=2*i+1, right=2*i+2, largest=i; if (left<len&&arr[left] >arr[largest]) { largest=left; } if (right<len&&arr[right] >arr[largest]) { largest=right; } if (largest!=i) { swap(arr, i, largest); heapify(arr, largest); } } functionswap(arr, i, j) { vartemp=arr[i]; arr[i] =arr[j]; arr[j] =temp; } functionheapSort(arr) { buildMaxHeap(arr); for (vari=arr.length-1; i>0; i--) { swap(arr, 0, i); len--; heapify(arr, 0); } returnarr; }
8.计数排序
functioncountingSort(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]--; } } returnarr; }
9.桶排序
functionbucketSort(arr, bucketSize) { if (arr.length===0) { returnarr; } vari; varminValue=arr[0]; varmaxValue=arr[0]; for (i=1; i<arr.length; i++) { if (arr[i] <minValue) { minValue=arr[i]; // 输入数据的最小值 } elseif (arr[i] >maxValue) { maxValue=arr[i]; // 输入数据的最大值 } } // 桶的初始化varDEFAULT_BUCKET_SIZE=5; // 设置桶的默认数量为5bucketSize=bucketSize||DEFAULT_BUCKET_SIZE; varbucketCount=Math.floor((maxValue-minValue) /bucketSize) +1; varbuckets=newArray(bucketCount); for (i=0; i<buckets.length; i++) { buckets[i] = []; } // 利用映射函数将数据分配到各个桶中for (i=0; i<arr.length; i++) { buckets[Math.floor((arr[i] -minValue) /bucketSize)].push(arr[i]); } arr.length=0; for (i=0; i<buckets.length; i++) { insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序for (varj=0; j<buckets[i].length; j++) { arr.push(buckets[i][j]); } } returnarr; }
10.基数排序
varcounter= []; functionradixSort(arr, maxDigit) { varmod=10; vardev=1; for (vari=0; i<maxDigit; i++, dev*=10, mod*=10) { for(varj=0; j<arr.length; j++) { varbucket=parseInt((arr[j] %mod) /dev); if(counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } varpos=0; for(varj=0; j<counter.length; j++) { varvalue=null; if(counter[j]!=null) { while ((value=counter[j].shift()) !=null) { arr[pos++] =value; } } } } returnarr; }
