Weitanai

# sort

img

# 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 快速排序

  • 颜色分类（荷兰国旗）

  • 正常排序数组

  • 颜色分类

给定一个包含红色、白色和蓝色，一共 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;
    }   
}

# 3 heapsort

  1. 堆构造阶段： 从右到左利用sink()构造子堆。从右中点sink()到左， 一半的有序， 后半部分就是叶子节点
  2. 下沉排序：

heaps.png

process .png

public class Heap{
    public static void sort(Comparable[] a){
    int n = a.length;
    for (int k = n/2; k >= 1; k--)
            sink(a, k, n);
    while (n > 1){
        exch(a, 1, n);
        sink(a, 1, --n);
    }
 }
    private static void sink(Comparable[] a, int k, int n){ /* as before */ }
    private static boolean less(Comparable[] a, int i, int j)
    { /* as before */ }
    private static void exch(Object[] a, int i, int j)
    { /* as before */ }

}

← 位运算 →