排序算法-快速排序

排序算法

1.冒泡排序

package sort;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {5,1,2,4,3};
        bubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void bubbleSort(int[] nums){
        int length = nums.length;
        //最多进行n-1趟排序
        for (int i= 0;i<length-1;i++){
            boolean flag = false;
            //设置下标为j的进行交换，每次有一个元素会落在最终位置，最值就不用再进行比较了
            //循环判断条件
            for (int j = 0;j<length-i-1;j++){
                if(nums[j]>nums[j+1]){
                    int temp = nums[j+1];
                    nums[j+1]=nums[j];
                    nums[j]=temp;
                    flag = true;
                }
            }
            //如果其中有一趟没有元素交换了，数组就基本有序了，结束排序（优化）
            if (flag == false){
                return;
            }
        }
    }
}

2.插入排序

package sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] nums = {4, 2, 1, 3};
        int length = nums.length;
        insertSort(nums, length);
    }

    //没有设置哨兵
    public static void insertSort(int[] nums, int length) {
        //i指向待排序的元素
        for (int i = 1; i < length; i++) {
            if (nums[i] < nums[i - 1]) {
                int insertKey = nums[i];
                //j指向已经排序号的元素
                int j;
                for (j = i - 1; j >= 0 && nums[j] > insertKey; j--) {
                    nums[j + 1] = nums[j];
                }
                nums[j + 1] = insertKey;
            }
        }
        System.out.println(Arrays.toString(nums));
    }
}

3.快速排序

package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
//        {6,1,2,7,9,3,4,5,10,8}
        int[] n = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int[] ren = sortArray(n);
        //将数组以String形式返回
        System.out.println(Arrays.toString(ren));;
    }

    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public static void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            //进行第一次划分
            int index = partition(nums, low, high);
            //递归
            quickSort(nums, low, index - 1);
            quickSort(nums, index + 1, high);
        }
    }

    //排序
    public static int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) {
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }

}