冒泡排序
function maopao(arr){
var length = arr.length,
num;
for(var i = 0; i < length; i++){
for(var j = 0; j < length - i - 1; j++){
if(arr[j] > arr[j + 1]){
num = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = num;
}
}
}
return arr;
}
選擇排序
function xuanze(arr){
var length = arr.length,
index,num;
for(var i = 0; i < length - 1; i++){
index = i;
for(var j = i + 1; j < length; j++){
if(arr[j] < arr[index]){
index = j;
}
}
if(index !== i){
num = arr[i];
arr[i] = arr[index];
arr[index] = num;
}
}
return arr;
}
插入排序
function charu(arr){
var length = arr.length,
num,index;
for(var i = 1; i < length; i++){
num = arr[i];
index = i - 1;
while(arr[index] > num && index >= 0){
arr[index + 1] = arr[index];
index--;
}
arr[index + 1] = num;
}
return arr;
}
歸并排序
function guibing(arr) { //采用自上而下的遞歸方法
var length = arr.length;
if(length <= 1) {
return arr;
}
var middle = Math.floor(length / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(guibing(left), guibing(right));
}
function merge(left, right){
var result = [];
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());
}
return result;
}
快速排序
function quickSort(arr, left, right){
var length = arr.length,
index,
left = typeof left === 'number' ? left : 0,
right = typeof right === 'number' ? right : length - 1;
if (left < right) {
index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
return arr;
}
function partition(arr, left ,right){ //分區操作
var pivot = left, //設定基準值(pivot)
index = pivot + 1;
for (var i = 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) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
也可以:
function kuaisu(arr){
var length = arr.length;
if(length < 2){
return arr;
}
var index = Math.floor(length / 2),
num = arr.splice(index, 1)[0],
left = [],
right = [];
arr.forEach(element => {
if(element > num){
right.push(element);
}else{
left.push(element);
}
});
return kuaisu(left).concat([num], kuaisu(right));
}
計數排序
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
基數排序
基數排序有兩種方法:
- MSD 從高位開始進行排序
- LSD 從低位開始進行排序
基數排序 vs 計數排序 vs 桶排序
這三種排序算法都利用了桶的概念,但對桶的使用方法上有明顯差異:
- 基數排序:根據鍵值的每位數字來配置設定桶
- 計數排序:每個桶隻存儲單一鍵值
- 桶排序:每個桶存儲一定範圍的數值
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
桶排序
桶排序是計數排序的更新版。它利用了函數的映射關系,高效與否的關鍵就在于這個映射函數的确定。
為了使桶排序更加高效,我們需要做到這兩點:
- 在額外空間充足的情況下,盡量增大桶的數量
- 使用的映射函數能夠将輸入的N個資料均勻的配置設定到K個桶中
同時,對于桶中元素的排序,選擇何種比較排序算法對于性能的影響至關重要。
什麼時候最快(Best Cases):
當輸入的資料可以均勻的配置設定到每一個桶中
什麼時候最慢(Worst Cases):
當輸入的資料被配置設定到了同一個桶中
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; //輸入資料的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; //輸入資料的最大值
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; //設定桶的預設數量為5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(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 (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
堆排序
堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法:
- 大頂堆:每個節點的值都大于或等于其子節點的值,在堆排序算法中用于升序排列
- 小頂堆:每個節點的值都小于或等于其子節點的值,在堆排序算法中用于降序排列
var len; //因為聲明的多個函數都需要資料長度,是以把len設定成為全局變量
function buildMaxHeap(arr) { //建立大頂堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { //堆調整
var left = 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);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
希爾排序
希爾排序是插入排序的一種更高效率的實作。它與插入排序的不同之處在于,它會優先比較距離較遠的元素。希爾排序的核心在于間隔序列的設定。既可以提前設定好間隔序列,也可以動态的定義間隔序列。動态定義間隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。在這裡,我就使用了這種方法。
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //動态定義間隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}