排序

• 冒泡排序
  比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至 正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

        function bubbleSort(arr) {
            var len = arr.length;
            for (var i = 0;i<len;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;
        }

        let arr = [8,2,9,10,12,11,3]
        console.log(bubbleSort(arr))

屏幕快照 2018-12-23 上午1.42.10.png

---

• 选择排序

选择排序算法是一种原址比较排序算法。
思路是：找到数据结构中的最小值并 将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

屏幕快照 2018-12-23 上午1.43.30.png

function selectionSort(arr) {
            let indexMin;
            for (let i = 0; i < arr.length - 1; i++){
                indexMin = i
                for (var j = i; j < arr.length; j++){ 
                    if(arr[indexMin] > arr[j]) {
                    indexMin = j
                }
                if (i !== indexMin){
                    let aux = arr[i]
                    arr[i] = arr[indexMin]
                    arr[indexMin] = aux
                }
            } 
            
            return arr
        }

        let arr = [44,38,5,47,15]

---

• 合并排序（分治策略）
  归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

  
  屏幕快照 2018-12-23 下午3.27.44.png
  屏幕快照 2018-12-23 下午3.32.27.png
  屏幕快照 2018-12-23 下午6.01.01.png

        let arr = [44,38,5,47,15]
       // 合并两个有序数组
        function merge(A,p,q,r){
            // A:数组
            // p:左半边开始位置
            // q:左半边结束,右半边开始位置
            // r:右半边结束
            let A1 = a.slice(p,q); // 存放左半边的临时空间
            let A2 = a.slice(q,r); // 存放右半边的临时空间

            A1.push(Number.MAX_SAFE_INTEGER);
            A2.push(Number.MAX_SAFE_INTEGER);
            
            for(let k = p , i = 0 , j = 0 ; k < r; k++ ){
                // k : 下一个写入位置
                // i : A1中回写位置
                // j : A2中回写位置
                A[k] = A1[i] < A2[j] ? A1[i++] : A2[j++]
            }
        }
        function merge_sort(A,p,r){
            // p : 开始位置
            // r : 结束位置
            if( r - p < 2 ) { return };
            const q = Math.ceil( ( p + r ) / 2 );
            // 排左半边
            merge_sort(A,p,q);
            // 排右半边
            merge_sort(A,q,r);
            // 合并两个有序数组
            merge(A,p,q,r);
        }

---

• 快速排序

  
  屏幕快照 2018-12-23 下午8.44.13.png
  屏幕快照 2018-12-23 下午9.47.00.png

  function merge_sort(A,p,r){
            // p : 开始位置
            // r : 结束位置
            if( r - p < 2 ) { return };
            const q = Math.ceil( ( p + r ) / 2 );
            // 排左半边
            merge_sort(A,p,q);
            // 排右半边
            merge_sort(A,q,r);
            // 合并两个有序数组
            merge(A,p,q,r);
        }


        function swap(A,i,j){
            [A[i],A[j]] = [A[j],A[i]]
        }
        function partition(A,lo,hi){
            // lo : 开始位置
            // hi : 结束位置
            
            // 找中间点,最后一位
            let pivot = A[hi-1];
            let i = lo,j = hi-1;
            //小于中心点范围：[lo,i]
            //未确认范围：[i,j]
            //大于中心点范围：[j,hi-1]
            while( i !== j){
                // 左边小于中心数字，左指针往后走
                if(A[i] <= pivot){
                    i++
                }else{ // 否则就交换位置，j往前
                    swap(A,i,j--)
                }
            }
            swap(A,j,--j)
            // 返回中心点位置
            return j
        }
        
        function qsort(A,lo = 0,hi = A.length){
            if(hi-lo <= 1) return 
            const p = partition(A,lo,hi)
            qsort(A,lo,p);
            qsort(A,p+1,hi);
        }