排序算法

排序

1.选择排序

时间复杂度O(n^2)，空间复杂度O(1)

int[] x = {15, 7, 12, 2, 8};
for (int z = 0; z < x.length - 1; z++) {//控制循环轮次
    int index = z;
    for (int i = z + 1; i < x.length; i++) {
        if (x[i] < x[index]) {
            index = i;//最小值的下标放在index
        }
    }
    if (index != z) {
        int temp = x[z];
        x[z] = x[index];
        x[index] = temp;
    }
    for (int a : x) {
        System.out.print(a + "\t");
    }
    System.out.println();
}

2.冒泡排序

时间复杂度O(n^2)，空间复杂度O(1)

int[] x={15,13,9,4,3,2};
for (int i = 1; i < x.length; i++) {//循环轮次
    for (int j = 0; j < x.length-1-i; j++) {
        if(x[j]>x[j+1]){
            int temp=x[j];
            x[j]=x[j+1];
            x[j+1]=temp;
        }
    }
    for (int a:x
         ) {
        System.out.println(a+"\t");
    }
}

5.插入排序

时间复杂度**O(n^2)**，空间复杂度O(1)

class Solution {
    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 插入排序
        for (int i = 1; i < len; i++) {
            int temp = nums[i]; // 临时变量用来保存当前值，赋值给前面
            int j = i;
            while (j > 0 && temp < nums[j - 1]) {
                // temp小于前面的数，然后就进行交换位置
                nums[j] = nums[j - 1];
                j--;
            }
            // 最后将这个临时变量赋值给 j
            nums[j] = temp;
        }
        return nums;
    }
}

4.快速排序

时间复杂度O(nlogn)，空间复杂度O(1)

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

    void quickSort(int[] nums, int i, int j) {
        // 定义start从前往后找比基准数大的数
        int start = i;
        // end从后往前找比基准数小的数
        int end = j;
        if (start > end) {
            return;
        }
        // 定义基准数
        int index = nums[i];

        // 不能先找前面大的，因为最后可能基准数不满足左边都比基准数小，右边都比基准数大
        while (start != end) {

            // 从后往前找比基准数小的，找到停止
            while (true) {
                if (start >= end || nums[end] < index) {
                    break;
                }
                end--;
            }

            // 从前往后找比基准数大的，找到停止
            while (true) {
                if (start >= end || nums[start] > index) {
                    break;
                }
                start++;
            }

            // 找到然后将两个数交换
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
        }

        // 最后相等了之后，就需要将基准数归位了
        int temp = nums[i]; // i就是第一个数
        nums[i] = nums[start]; // start 是基准数
        nums[start] = temp;

        // 递归去将基准数的左边和右边也按照这个去排序
        quickSort(nums, i, start - 1);
        quickSort(nums, start + 1, j);
    }
}