Sort

参考: 图例

蓝色
~~ 数组的初始状态
红色
~~ 一次循环后的状态
紫色
~~ 最后排序完成的状态
黄色
~~ 即将赋值给其他元素
绿色
~~ 待替换值的元素
N
~~ N 表示数组中有多少个元素

一、冒泡排序

时间复杂度 O(n^2)（两个嵌套循环，第一次循环 n 次，第二次循环 n - 1 次，第三次循环 n - 2 次。。。）

下面举例的是正向排序，从小到大；如果需要更换为倒序，则替换判断条件即可

---

第一次内部循环

☞第 1 个元素，比较 a[0] 和 a[1] 的大小，如果 a[0] > a[1]，则进行替换；否则不进行任何操作
☞第 2 个元素，比较 a[1] 和 a[2] 的大小，如果 a[1] > a[2]，则进行替换；否则不进行任何操作
。。。
☞第 n-1 个元素，比较 a[n-1] 和 a[n] 的大小，如果 a[n-1] > a[n]，则进行替换；否则不进行任何操作

在经过第一次内部循环后，将 a 中的 最大值 放在了最后一位

---

所以第二次内部循环，不需要包括最后一位，只循环 n-1 次

第二次内部循环

☞第 1 个元素，比较 a[0] 和 a[1] 的大小，如果 a[0] > a[1]，则进行替换；否则不进行任何操作
☞第 2 个元素，比较 a[1] 和 a[2] 的大小，如果 a[1] > a[2]，则进行替换；否则不进行任何操作
。。。
☞第 n-2 个元素，比较 a[n-2] 和 a[n-1] 的大小，如果 a[n-2] > a[n-1]，则进行替换；否则不进行任何操作

在经过第二次内部循环之后，将 a 中的 次大值 放在了次高位置

---

第 N-1 次内部循环

☞第一个开始，比较 a[0] 和 a[1] 的大小，如果 a[0] > a[1]，则进行替换；否则不进行任何操作

在经过第 N-1 次内部循环之后，就可以得出排序结果。

👇下面是具体的排序过程示例图

冒泡排序

代码实现

for(int i = 0; i < arr.count; i++) {
    for(int j = 0; j < arr.count - 1 - i; j++) {
        if (arr[j+1] < arr[j]) { // 倒序替换为 arr[j+1] > arr[j]
              int temp = arr[j];
              arr[j] = [j+1];
              arr[j+1] = temp;
        }
    }
}

二、插入排序

时间复杂度 O(n^2)

☞ 从 i(i > 1) 开始并逐次递增到 n-1，，将 a[i] 插入 a[1...i-1] 中适当的位置 —— 即将 i 插入已排好的排序 a[1...i-1] 中

下面举例的是正向排序，从小到大；如果需要更换为倒序，则替换判断条件即可

---

第一次循环

取出 2 个元素 a[temp] = a[1]
☞ 第 1 个元素 a[0]，a[temp] < a[0]，a[1] = a[0] 和 a[0] = a[temp]；否则不进行任何操作

---

第二次循环

取出 3 个元素 a[temp] = a[2]
☞ 第 2 个元素 a[1]，a[temp] < a[1]，a[2] = a[1] 和 a[1] = a[temp]；否则不进行任何操作
☞ 第 1 个元素 a[0]，a[temp] < a[0]，a[1] = a[0] 和 a[0] = a[temp]；否则不进行任何操作

---

第 N-1 次循环

取出 N 个元素 a[temp] = a[n-1]
☞ 第 N-1 个元素 a[n-2]，a[temp] < a[n-2]，a[n-1] = a[n-2] 和 a[n-2] = a[temp]；否则不进行任何操作
☞ 第 N-2 个元素 a[n-3]，a[temp] < a[n-3]，a[n-2] = a[n-3] 和 a[n-3] = a[temp]；否则不进行任何操作
。。。
☞ 第 1 个元素 a[0]，a[temp] < a[0]，a[1] = a[0] 和 a[0] = a[temp]；否则不进行任何操作

---

👇下面是具体的排序过程示例图

插入排序

代码实现

for(int i = 1; i < arr.count; i++) {
    int temp = arr[i];
    for(int j = i-1; j >=0 && temp < arr[j]; j--) { // 倒序替换为 j >=0 && temp > arr[j]
        arr[j+1] = a[j];
        arr[j] = temp;
    }
}

三、选择排序

时间复杂度 O(n^2)

将 a[i] 和 a[i...n-1] 逐个元素进行比较并根据条件进行替换

下面举例的是倒序排序，从大到小；如果需要更换为正向排序，则替换判断条件即可

---

第一次循环

☞ 第 1 个元素，a[0] < a[1]， a[0] 和 a[1] 进行替换；否则不进行任何操作
☞ 第 1 个元素，a[0] < a[2]， a[0] 和 a[2] 进行替换；否则不进行任何操作
☞ 第 1 个元素，a[0] < a[3]， a[0] 和 a[3] 进行替换；否则不进行任何操作
。。。
☞ 第 1 个元素，a[0] < a[n-1]， a[0] 和 a[n-1] 进行替换；否则不进行任何操作

---

第二次循环

☞ 第 2 个元素，a[1] < a[2]，a[1] 和 a[2] 进行替换；否则不进行任何操作
☞ 第 2 个元素，a[1] < a[3]，a[1] 和 a[3] 进行替换；否则不进行任何操作
。。。
☞ 第 2 个元素，a[1] < a[n-1]， a[1] 和 a[n-1] 进行替换；否则不进行任何操作

---

第 N-1 次循环

☞ 第 N-1 个元素，a[n-2] < a[n-1]，a[n-2] 和 a[n-1] 进行替换；否则不进行任何操作

---

👇下面是具体的排序过程示例图

选择排序

代码实现

for(int i = 0; i < arr.count; i++) {
    for(int j = i+1; i < arr.count; j++) { 
        if(arr[i] < a[j]) { // 正向排序替换为 arr[i] > a[j]
            int temp = a[i];
            arr[j] = a[i];
            arr[i] = temp;
        }
    }
}

四、快速排序

时间复杂度为 O(nlogn)

快速排序利用二分法

---

1. 先以一个数为基准（最左边的值），然后定义左、右两个指针（数组的边缘），两个指针往中间进行寻找

👉 左边的指针寻找比基数大的指针
👈 右边的指针寻找比基数小的指针

2. 最后将左、右指针的值进行替换，然后两个指针再次往中间进行寻找

👉 左边的指针寻找比基数大的指针
👈 右边的指针寻找比基数小的指针

3. 直到两个指针重复，此时指向的地方我们暂时称为 "中间指针"

4. 以这个中间指针为基准分开两个数组

5. 然后再分别对每个数组进行👆重复步骤，直到每个数组剩下的元素个数为 2，则无需再排序

---

👇下面是具体的排序过程示例图

快速排序

代码实现

- (void)sortWithLeftIndex:(int)left rightIndex:(int)right {
    if(left < right) {
        int middle = [self getMiddleIndexAndSortWithLeftIndex:left rightIndex:right];
        [self getMiddleIndexAndSortWithLeftIndex:left rightIndex:middle - 1];
        [self getMiddleIndexAndSortWithLeftIndex:middle rightIndex:right];
    }
}

- (int)getMiddleIndexAndSortWithLeftIndex:(int)left rightIndex:(int)right {

    int base_value = arr[left];
    while(left < right) {   
        while(left < right && base_value<=arr[right]) {
            right--;
        }
        if(left < right) {
            arr[left] = arr[right];
        }
        
        while(left < right && base_value>=arr[left]) {
            left++;
        }

        if(left < right) {
            arr[right] = arr[left];
        }
    }
    arr[left] = base_value;
    return left;
}