排序算法

冒泡排序

初步实现

两次完整遍历数组

1. 依次比较数组中相邻两个元素大小，若a[i]>a[i+1]则交换两个元素，两两都比较一遍称为冒泡，结果是让最大的元素排至最后。
2. 重复以上步骤，直到整个数组有序。

减少比较次数

两次循环，一个遍历length次，另一个遍历length - i次。

减少冒泡次数

一次遍历后未发生交换时说明数组有序。

进一步优化

最后一次交换的索引可以作为下一轮冒泡的比较次数。若为零，表示整个数组有序。

public static void main(String[] args){
    int n = a.length - 1;
        for(;;){
            int last = 0;
            for(int j = 0;j < n;j++){
                if(a[j] > a[j + 1]){
                    swap(a,j,j+1);
                    last = j;
                }
            }
            n = last;
            if(n == 0){
                return;
            }
            System.out.println(Arrays.toString(a));
        }
}

public static void swap(int[] a,int i,int j){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

选择排序

实现

1. 将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集
2. 重复以上步骤，直到整个数组有序

优化方式

1. 为了减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素

与冒泡排序相比

1. 平均时间复杂度都是O(n^2)
2. 选择排序一般快于冒泡，因为交换次数少
3. 但如果集合有序度高，冒泡优于选择
4. 冒泡属于稳定排序算法，而选择属于不稳定排序

public static void selection(int[] a){
    for (int i = 0; i < a.length - 1; i++){
        int s = i;
        for (int j = s + 1; j < a.length; j++){
            if(a[s] > a[j]){
                s = j;
            }
        }
        if(s != i){
            swap(a,s,i);
        }
        System.out.println(Arrays.toString(a));
    }
}

插入排序

实现

1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）
2. 重复以上步骤，直到整个数组有序

优化方式

1. 待插入元素进行比较，遇到比自己小的元素，就代表找到了插入位置，无需进行后续比较
2. 插入时可以直接移动元素，而不是交换元素

与选择排序比较

1. 二者平均时间复杂度都是O(n^2)
2. 大部分情况下，插入都略优于选择
3. 有序集合插入的时间复杂度为O(n)
4. 插入属于稳定排序算法，选择属于不稳定排序

public static void insert(int[] a){
    for(int i = 1; i < a.length; i++){
        int temp = a[i];
        int j = i - 1;
        while(j >= 0){
            if(temp < a[j]){
                a[j + 1] = a[j];
            } else {
                break;
            }
            j--;
        }
        a[j + 1] = temp;
        System.out.println(Arrays.toString(a));
    }
}

希尔排序

快速排序

实现

1. 每一轮拍寻选择一个基准点(pivot)进行分区
   1. 让小于基准点的元素进入一个分区，大于基准的元素进入另一个分区
   2. 当分区完成时，基准点元素的位置就算其最终位置
2. 在子分区重复以上过程，直至子分区元素个数少于等于1，体现的是分而治之的思想(divide-and-conquer)
3. 单边循环快排（lomuto洛穆托分区方案）
   1. 选择最右元素作为基准点元素
   2. j指针负责找到比基准点小的元素，一旦找到则与i进行交换
   3. i指针维护小于基准点元素的边界，也就是每次交换的目标索引
   4. 最后基准点与i交换，i即为分区位置
4. 双边循环快排（并不完全等价于hoare霍尔分区方案）
   1. 选择最左元素作为基准点元素
   2. j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i，j相交
   3. 最后基准点与i（此时i与j相等）交换，i即为分区位置

归并排序

计数排序

基数排序