排序总结

冒泡排序

原理：每次比较两个相邻的元素，将较大元素交换至右端 特点：每次循环结束，会出现一个排序好的元素，右侧 理解：大的数右移，重复此过程 代码：

public static void bubbleSort(int[] nums){
        for (int i=0; i<nums.length-1; i++){        //第i次循环找出第i小的元素0<=i<=length-1
            for (int j=0; j<nums.length-1-i; j++){
                if (nums[j+1]<nums[j]){
                    int tmp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tmp;
                }
                for (int num : nums) System.out.print(num+"\t");
                System.out.println();
            }
        }
    }

优化：使用flag标记是否已经有序

选择排序

原理：每次循环找出最小的元素于左侧，每次循环都从剩余未排序系列找出最小的元素 代码：

/**
     * 选择排序
     * @param nums
     */
    public static void selectSort(int[] nums){
        int len = nums.length;
        if (len==0 || len==1) return;
        for (int i=0; i<len; i++){
            for (int j=i+1; j<len; j++){
                if (nums[j] < nums[i]){
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
    }

插入排序

原理：递归思想，假设第一个有序，则新插入一个，将其排序，循环递归 代

/**
     * 插入排序
     * @param nums
     */
    public static int[] insertSort(int[] nums, int index){
        if (index == nums.length) return nums;
        for (int i=0; i<index; i++){
            if (nums[index]<nums[i]){
                int tmp = nums[index];
                nums[index] = nums[i];
                nums[i] = tmp;
            }
        }
        return insertSort(nums, index+1);
    }

堆排序

原理：利用堆的特性 代码：

/**
     * 堆排序
     * @param nums
     */
    public static void heapSort(int[] nums){
        initHeap(nums);
        int count = nums.length;
        while (count>1){
            int tmp = nums[count-1];
            nums[count-1] = nums[0];
            nums[0] = tmp;
            count--;
            adjustHeap(nums,count,0);
        }
    }
    public static void initHeap(int[] nums){
        for (int root=nums.length/2-1; root>=0; root--){
            adjustHeap(nums,nums.length, root);
        }
    }
    public static void adjustHeap(int[] nums, int count, int root){
        int maxChildIndex;
        while (root<=count/2-1){
            if (root==count/2-1 && count%2==0){
                maxChildIndex = 2*root+1;
            }else {
                int leftChildIndex = 2 * root + 1;
                int rightChildIndex = 2 * root + 2;
                maxChildIndex = nums[leftChildIndex] > nums[rightChildIndex]?leftChildIndex:rightChildIndex;
            }
            if (nums[root] < nums[maxChildIndex]){
                int tmp = nums[root];
                nums[root] = nums[maxChildIndex];
                nums[maxChildIndex] = tmp;
                root = maxChildIndex;
            }else {
                return;
            }
        }
    }