leetcode 101 chapter 5 排序算法

    1. /**
    2. *    采用前包后不包的策略
    3. **/
    4. void quick_sort(int[] nums,int left, int right){
    5.         //说明索引范围少于等于1个
    6.         if(left >= right-1) return;
    7.         //两个指针指向开头与结尾，取第一个作为基准值
    8.         int first = left,last = right-1,key = nums[first];
    9.         while(first < last){
    10.             while(first < last && nums[last] >= key) last--;
    11.             nums[first] = nums[last];
    12.             while(first < last && nums[first] <= key) first++;
    13.             nums[last] = nums[first];
    14.         }
    15.         nums[first] = key;
    16.         quick_sort(nums,left,first);
    17.         quick_sort(nums,first+1,right);
    18.     }
    1. void merge_sort(int[] nums, int left, int right, int[] temp){
    2.         if (left >= right - 1) return;//只有少于等于1个元素，这里采取前闭后开
    3.         int middle = left + (right - left) / 2;
    4.         merge_sort(nums,left,middle,temp);
    5.         merge_sort(nums,middle,right,temp);
    7.         int p = left, q = middle, i = left;//p是左半区间起始位置，q是右半区间起始，i是temp的起始位置
    8.         while (p < middle || q < right){
    9.             //合并过程
    10.             if (q >= right || (p < middle && nums[p] < nums[q])) temp[i++] = nums[p++];
    11.             else temp[i++] = nums[q++];
    12.         }
    13.         //将合并结果赋值给nums数组
    14.         for (i = left; i < right; i++) {
    15.             nums[i] = temp[i];
    16.         }
    17.     }
    1. void insertion_sort(int[] nums, int n) {
    2.     for (int i = 0; i < n; ++i) {
    3.         for (int j = i; j > 0 && nums[j] < nums[j-1]; --j) {
    4.             swap(nums[j], nums[j-1]);
    5.         }
    6.     }
    7. }

    桶排序
    桶排序错采取的策略是创建n个桶，在桶里可以存放任意多个相同类型的数，本身不同的桶是排好序的，然后再对桶内进行排序，就可以将所有数进行排序。
    桶排序的时间复杂度为O(n)，空间复杂度为O(n);