几种经典排序算法原理

几种经典排序算法的原理

参考自：十大经典排序算法

快速排序

1. 从数列中挑出一个元素，称为 “基准”
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排

   function quickSort(arr, left, right) {
     var len = arr.length,
       partitionIndex,
       left = typeof left != 'number' ? 0 : left,
       right = typeof right != '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) {     // 分区操作
     var pivot = left,                      // 设定基准值
       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
   }

冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

   function bubbleSort(arr) {
     var len = arr.length
     for (var i = 0; i < len - 1; i++) {
       for (var j = 0; j < len - 1 - i; j++) {
         if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
           var temp = arr[j+1]       // 元素交换
           arr[j+1] = arr[j]
           arr[j] = temp
         }
       }
     }
     return arr
   }

选择排序

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3. 重复第二步，直到所有元素均排序完毕

   function selectionSort(arr) {
     var len = arr.length
     var minIndex, temp
     for (var i = 0; i < len - 1; i++) {
       minIndex = i
       for (var j = 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. 拿10个桶，多次使用。首先以个位数的值进行装桶，即个位数为1则放入1号桶，为9则放入9号桶。装完后拿出来，接着再次入桶，不过这次以十位数的数字为准

   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
   }

计数排序–每个桶只存储单一键值

1. 将输入的数据值转化为键存储在额外开辟的数组空间中

   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
   }

桶排序–每个桶存储一定范围的数值

1. 桶排序是计数排序的升级版。它利用了函数的映射关系

   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
   }

插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

   function insertionSort(arr) {
     var len = arr.length
     var preIndex, current
     for (var i = 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
   }

希尔排序

1. 也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法
2. 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
3. 待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序

   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
   }

堆排序

堆可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示，每一个结点对应数组中的一个元素
二叉堆一般分为两种：最大堆和最小堆。最大堆：堆中每个父节点的元素值都大于等于其孩子结点（如果存在），这样的堆就是一个最大堆，因此，最大堆中的最大元素值出现在根结点(堆顶)

1. 堆排序就是把堆顶的最大数取出
2. 将剩余的堆继续调整为最大堆
3. 剩余部分调整为最大堆后，再次将堆顶的最大数取出，再将剩余部分调整为最大堆
4. 这个过程持续到剩余数只有1个时结束

   var len  // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
   
   function heapSort(arr) {
     buildMaxHeap(arr)
   
     for (var i = arr.length-1; i > 0; i--) {
       swap(arr, 0, i)
       len--
       heapify(arr, 0)
     }
     return arr;
   }
   
   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
   }

归并排序

1. 把原始数组分成若干子数组，对每一个子数组进行排序，继续把子数组与子数组合并，合并后仍然有序，直到全部合并完，形成有序的数组
2. 始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间

   function mergeSort(arr) {  // 采用自上而下的递归方法
     var len = arr.length
     if(len < 2) {
       return arr
     }
     var middle = Math.floor(len / 2),
       left = arr.slice(0, middle),
       right = arr.slice(middle)
     return merge(mergeSort(left), mergeSort(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
   }