快速排序

快速排序是一种非常常用的排序方式，记录一下原理，举个例子
有这么一串数字(int)

7, 5, 3, 2, 9, 10, 8, 4, 6, 1
使用快速排序原理如下图

1. 第一步：找基准值

• 取第一个为基准值
• i从向右找比基准值大的数
• j从向左找比基准值小的数

开始

2. 第二步：找到了，如果i < j, 交换两个数

找到了 i < j, 交换两个数

3. 第三步：继续查找

找到了
i < j, 交换两个数
找到了
i < j, 交换两个数

---

4. 第四步：i == j(关键部分来了)

i == j, 此时i和j指向同一个值
还记得基准值吗？
基准值和 i 交换

相当于把此基准值放到它应该在的位置，把7放到第七个位置，7在所有数字中排行第七。（有点绕！）

5. 第五步：从i左右分成两个数组，重新进行上述步骤

重复啊重复

void fastSort(int left, int right, int array[], int lenth)  {
    /**
     1. 选取基准值，第一个数
     2. 从首段开始，找到一个比基准值大的数
     3. 从尾部开始，找到一个比基准值小的数
     4. 如果i, j 不相等，则交换两个数
     5. 相等，则将基准值和 i 位置数值交换
     6. 递归i左侧和右侧
     */
    
    int i = left;
    int j = right;
    if (left > right) {
        return;
    }
    //选取基准值
    int temp = array[left];
    while (i != j) {
        
        while (array[j] >= temp && i < j) {
            j--;
        }
        
        while (array[i] <= temp && i < j) {
            i++;
        }
        
        
        if (i < j) {
            int t = 0;
            t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
        
    }
    array[left] = array[i];
    array[i] = temp;
    printArray(array, lenth);
    fastSort(left, i - 1, array, lenth);
    fastSort(i + 1, right, array, lenth);
    
}

老规矩 代码