package com.sf.leetcode;

import java.util.Arrays;

public class Solution_912 {

    // 排序算法有哪些：比较类排序和非比较类排序
    // 比较类排序：冒泡 快排 插入 希尔 选择 堆 归并
    // 非比较类排序：桶 计数 基数

    // 选择排序
    // 找到数组中最小的元素，然后和第一个元素交换，继续找到剩余元素中的最小值，和第二个元素交换，以此类推
    // 时间复杂度 O(n^2)
    public static int[] selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // 记录当前的最小值 所在的索引位置
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = nums[min];
                nums[min] = nums[i];
                nums[i] = temp;
            }
        }

        return nums;
    }

    // 插入排序
    // 对于一组有序数据，第一个元素是天然有序，从第二个元素开始，如果比第一个元素大，那么就可以直接放在后面
    // [2,4]
    // [1,2,4]
    // 时间复杂度 O(n^2)
    public static int[] insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            // 从当前位置往前遍历
            for (int j = i; j > 0; j--) {
                // 如果当前元素比前一个元素大 结束处理
                if (nums[j] > nums[j - 1]) break;
                int temp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = temp;
            }
        }
        return nums;
    }

    // 冒泡排序
    // 两两比较相邻元素 将更大的元素后移 一轮冒泡后确保最大的元素在最后一个位置
    public static int[] bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                // 如果当前元素 比 后一个元素大 交换
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 4, 5, 2, 1, 6, 7, 8, 9};
//        selectionSort(nums);
//        insertionSort(nums);
        bubbleSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}