快速排序
通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序[序列]
流程
快速排序算法通過多次比較和交換來實現(xiàn)排序，其排序流程如下： [2]
(1)首先設(shè)定一個分界值，通過該分界值將數(shù)組分成左右兩部分。 [2]
(2)將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊。此時，左邊部分中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值。 [2]
(3)然后，左邊和右邊的數(shù)據(jù)可以獨立排序。對于左側(cè)的數(shù)組數(shù)據(jù)，又可以取一個分界值，將該部分數(shù)據(jù)分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理。 [2]
(4)重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側(cè)部分排好序后，再遞歸排好右側(cè)部分的順序。當左、右兩個部分各數(shù)據(jù)排序完成后，整個數(shù)組的排序也就完成了。
代碼及注釋
看代碼注釋
//
// SCXQuickSoft.m
// TestArithmetic
//
// Created by 孫承秀 on 2020/7/14.
// Copyright ? 2020 孫承秀. All rights reserved.
//
#import "SCXQuickSoft.h"
@interface SCXQuickSoft()
@property(nonatomic,strong) NSMutableArray *softArr;
@end
@implementation SCXQuickSoft
-(NSArray *)soft:(NSArray<NSNumber *> *)arr{
NSMutableArray *soft = arr.mutableCopy;
self.softArr = soft;
[self beginSoft:0 end:soft.count];
return soft.copy;
}
- (void)beginSoft:(NSInteger)begin end:(NSInteger)end{
if (end - begin < 2) {
return;
}
// 找到軸點，然后依次在進行分割
// 時間復雜度 O(n)
NSInteger pivotIndex = [self pivotIndex:begin end:end];
// 左半邊
// T(n/2)
[self beginSoft:begin end:pivotIndex];
// 右半邊
// T(n/2)
[self beginSoft:pivotIndex+1 end:end];
// 如果左右分布均勻，此時為最好的情況想，總時間復雜度 T(n) = 2 * T(n/2) + O(n) = O(nlogn)
// 如果分布不均勻，如，7，6，5，4，3，2，1，7 為軸點，7右邊的都比7小，那么需要將每一個都調(diào)到7的左邊
// T(n) = T(n - 1) + O(n) =O(n^2)
}
/// 獲取軸點位置，也就是那個分割點的位置，每次將序列分為兩個，這個分割點的左邊都比這個軸點小，右邊都比這個軸點大
/// @param begin 開始位置
/// @param end 結(jié)束位置
- (NSInteger)pivotIndex:(NSInteger)begin end:(NSInteger)end{
/*
1.取出第一元素來一次進行比較，從后往前比較
2.如果后面的元素比當前元素大，那么不用動，然后end--
,如果發(fā)現(xiàn)后面的元素小于等于當前軸點元素，那么將end的位置的元素，
覆蓋當前begin位置的元素，然后從begin開始比較,
調(diào)到步驟3
3.如果發(fā)現(xiàn)當前元素大小比軸點元素大小小，那么begin++，
如果當前元素比軸點元素大，那么將begin位置的元素賦值給end，
然后再從end往回比較，
調(diào)到步驟2.
*/
// 為了優(yōu)化，隨機選擇一個元素和begin位置元素作為交換，不要每次都選第一個，有局限性
int rand = begin + (arc4random() %(end - begin + 1));
NSNumber *tmp = self.softArr[begin];
self.softArr[begin] = self.softArr[rand];
self.softArr[rand] = tmp;
// 1. 取出來第一個元素，當做軸點元素,備份
NSNumber *first = self.softArr[begin];
// 最后一個元素的位置
end --;
// begin 和 end 沒有重合
while (begin < end) {
// 最后一個元素，從后往前走
while (begin < end) {
// 取出最后一個元素，然后和軸點元素比較
NSNumber *last = self.softArr[end];
// 2. 從后往前比較，如果后面的比前面大，那么不用交換，end--
if (last.intValue > first.intValue) {
// 2. 后面的大，一直往前走就可以
end --;
} else {
// 2. 后面的比前面的小或者等于，需要調(diào)換位置
// 2. 將end元素覆蓋到begin位置，然后begin++，然后調(diào)用，從begin開始，從前往后比較。
self.softArr[begin++] = last;
break;
}
}
// 如果這時候begin和end重合了，那么久說明找到了
// 3.如果沒有重合，就說明掉頭了，需要從前往后走
while (begin < end) {
// 3。取出第一個元素，和當前軸點元素作比較
NSNumber *last = self.softArr[begin];
// 3.如果當前元素比軸點元素小，那么只需要begin++ 就可以，繼續(xù)向后找
// 等于放到下面是為了均勻分割，分布均勻之后，效率會大大增高，差別很大
if (first.intValue > last.intValue) {
begin ++;
} else {
// 3. 如果當前位置元素比軸點元素大，那么需要將這個begin位置的元素，覆蓋到end位置，然后end--；
// 2. 然后跳到步驟2，從后往前走
self.softArr[end--] = last;
break;;
}
}
}
// 然后將備份的元素放到軸點位置
self.softArr[begin] = first;
// 當開始哨兵和結(jié)束的哨兵位置重合的時候，就是軸點的位置，說明已經(jīng)分割好了
return begin;
}
@end
時間復雜度
// 時間復雜度 O(n)
NSInteger pivotIndex = [self pivotIndex:begin end:end];
// 左半邊
// T(n/2)
[self beginSoft:begin end:pivotIndex];
// 右半邊
// T(n/2)
[self beginSoft:pivotIndex+1 end:end];
// 如果左右分布均勻，此時為最好的情況想，總時間復雜度 T(n) = 2 * T(n/2) + O(n) = O(nlogn)
// 如果分布不均勻，如，7，6，5，4，3，2，1，7 為軸點，7右邊的都比7小，那么需要將每一個都調(diào)到7的左邊
// T(n) = T(n - 1) + O(n) =O(n^2)
