sort

0 bubble

let a = [1, 3, 7, 2, 4];
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

0.5选择排序

class Solution {
   public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;//每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                exch(arr,min,i);
            }
        }
    } 
    private void exch(int[] nums, int i, int j){
        int t =nums[i];
        nums[i] = nums[j];
        nums[j] =t;
    }   
}

1 插入排序

class Solution {
    public int[] sortArray(int[] nums) {
        int len= nums.length;
        for(int i = 0; i<len; i++){
                for(int j = i; j>0  && (nums[j] <nums[j-1]); j--){
                    // j>0 不等于0 , 因为nums[j] <nums[j-1]
                        exch(nums, j-1, j);        
                }
        }
        return nums;   
    }
    private void exch(int[] nums, int i, int j){
        int t =nums[i];
        nums[i] = nums[j];
        nums[j] =t;
    }   
}

2 mergeSort

3 快速排序

• 颜色分类（荷兰国旗）

• 正常排序数组

• 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length-1;
        int lo = 0, i = lo;
        //key i开始的位置， 与确定大小的元素对比时 从0开始
        //                   与第一个元素相比的时候(sort array);
            while(i <= len){
                if(nums[i] < 1){
                swap(nums,i++, lo++);
                }
                else if(nums[i] > 1){
                    swap(nums, i, len--);
                }
                else{
                    i++;
                }
            }
    }
    private void swap(int[]nums, int i , int j){
        int t  = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

• 排序数组
• nums = { 2,4,5,1,4,8,3};

class Solution {
    public int[] sortArray(int[] nums) {   
        quick(nums, 0, nums.length-1);
        return nums;
    }
    public void quick(int[] nums, int lo, int hi){
        if(hi<=lo) return; 
        int lt = lo, i = lo+1, gt = hi;
        int c = nums[lo];
        while(i<=gt){
            if(nums[i] < c ){
                exch(nums, i++, lt++);
            }
            else if(nums[i]> c){
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        quick (nums,lo, lt-1);
        quick(nums,gt+1, hi);
    }
    private void exch(int[] nums, int i, int j){
        int t =nums[i];
        nums[i] = nums[j];
        nums[j] =t;
    }   
}

快排1

• 首先patittion，

        运用双指针的方法<br />最后交换 flag 与数组后段的下标
  

• 递归排序左右两边的数组

quick3

• 选择flag
• 第一次遍历数组，与flag比较

• 
  

  function quick3(arr, lo, hi) {
    let lt = lo,
        i = lo + 1,
        gt = hi;
    if (hi < lo) return;
    let v = arr[lo];
    while (i <= gt) {
        if (arr[i] > v) exch(arr, lt++, i++);
        else if (arr[i] < v) exch(arr, i, gt--);
        else i++;
    }
  
    quick3(arr, lo, lt - 1);
    quick3(arr, gt + 1, hi);
  }