用Objective-C實(shí)現(xiàn)幾種基本的排序算法，并把排序的過程圖形化顯示肛真。其實(shí)算法還是挺有趣的 ^ ^.
- 選擇排序
- 冒泡排序
- 插入排序
- 快速排序
選擇排序
以升序?yàn)槔?br> 選擇排序比較好理解谐丢，一句話概括就是依次按位置挑選出適合此位置的元素來填充。
- 暫定第一個(gè)元素為最小元素蚓让，往后遍歷庇谆，逐個(gè)與最小元素比較，若發(fā)現(xiàn)更小者凭疮，與先前的"最小元素"交換位置饭耳。達(dá)到更新最小元素的目的。
- 一趟遍歷完成后执解，能確保剛剛完成的這一趟遍歷中寞肖，最的小元素已經(jīng)放置在前方了。然后縮小排序范圍衰腌，新一趟排序從數(shù)組的第二個(gè)元素開始新蟆。
- 在新一輪排序中重復(fù)第1、2步驟右蕊，直到范圍不能縮小為止琼稻，排序完成。
選擇排序.gif
以下方法在NSMutableArray+JXSort.m中實(shí)現(xiàn)
- (void)jx_selectionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
if (self.count == 0) {
return;
}
for (NSInteger i = 0; i < self.count - 1; i ++) {
for (NSInteger j = i + 1; j < self.count; j ++) {
if (comparator(self[i], self[j]) == NSOrderedDescending) {
[self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];
}
}
}
}
冒泡排序
- 在一趟遍歷中饶囚，不斷地對(duì)相鄰的兩個(gè)元素進(jìn)行排序帕翻，小的在前大的在后鸠补，這樣會(huì)造成大值不斷沉底的效果，當(dāng)一趟遍歷完成時(shí)嘀掸，最大的元素會(huì)被排在后方正確的位置上紫岩。
- 然后縮小排序范圍，即去掉最后方位置正確的元素睬塌，對(duì)前方數(shù)組進(jìn)行新一輪遍歷泉蝌，重復(fù)第1步驟。直到范圍不能縮小為止揩晴，排序完成勋陪。
冒泡排序.gif
- (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
if (self.count == 0) {
return;
}
for (NSInteger i = self.count - 1; i > 0; i --) {
for (NSInteger j = 0; j < i; j ++) {
if (comparator(self[j], self[j + 1]) == NSOrderedDescending) {
[self jx_exchangeWithIndexA:j indexB:j + 1 didExchange:exchangeCallback];
}
}
}
}
插入排序
插入排序是從一個(gè)亂序的數(shù)組中依次取值，插入到一個(gè)已經(jīng)排好序的數(shù)組中硫兰。
這看起來好像要兩個(gè)數(shù)組才能完成粥鞋，但如果只想在同一個(gè)數(shù)組內(nèi)排序，也是可以的瞄崇。此時(shí)需要想象出兩個(gè)區(qū)域：前方有序區(qū)和后方亂序區(qū)。
- 分區(qū)壕曼。開始時(shí)前方有序區(qū)只有一個(gè)元素苏研，就是數(shù)組的第一個(gè)元素。然后把從第二個(gè)元素開始直到結(jié)尾的數(shù)組作為亂序區(qū)腮郊。
- 從亂序區(qū)取第一個(gè)元素摹蘑，把它正確插入到前方有序區(qū)中。把它與前方無序區(qū)的最后一個(gè)元素比較轧飞，亦即與它的前一個(gè)元素比較衅鹿。
- 如果比前一個(gè)元素要大，則不需要交換过咬，這時(shí)有序區(qū)擴(kuò)充一格大渤，亂序區(qū)往后縮減一格，相當(dāng)于直接拼在有序區(qū)末尾掸绞。
- 如果和前一個(gè)元素相等泵三，則繼續(xù)和前二元素比較、再和前三元素比較......如果往前遍歷到頭了衔掸，發(fā)現(xiàn)前方所有元素值都長(zhǎng)一個(gè)樣的話(囧)烫幕，那也可以，不需要交換敞映，這時(shí)有序區(qū)擴(kuò)充一格较曼，亂序區(qū)往后縮減一格，相當(dāng)于直接拼在有序區(qū)末尾振愿。如果比前一個(gè)元素大呢捷犹？對(duì)不起作為有序區(qū)不可能出現(xiàn)這種情況弛饭。如果比前一個(gè)元素小呢，請(qǐng)看下一點(diǎn)伏恐。
- 如果比前一個(gè)元素小孩哑，則交換它們的位置。交換完后翠桦，繼續(xù)比較取出元素和它此時(shí)的前一個(gè)元素横蜒，若更小就交換，若相等就比較前一個(gè)销凑，直到遍歷完成丛晌。
至此，把亂序區(qū)第一個(gè)元素正確插入到前方有序區(qū)中斗幼。
- 往后縮小亂序區(qū)范圍澎蛛，繼續(xù)取縮小范圍后的第一個(gè)元素，重復(fù)第2步驟蜕窿。直到范圍不能縮小為止谋逻，排序完成。
插入排序.gif
- (void)jx_insertionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
if (self.count == 0) {
return;
}
for (NSInteger i = 1; i < self.count; i ++) {
for (NSInteger j = i; j > 0 && comparator(self[j], self[j - 1]) == NSOrderedAscending; j --) {
[self jx_exchangeWithIndexA:j indexB:j - 1 didExchange:exchangeCallback];
}
}
}
快速排序
快排的版本有好幾種桐经，粗略可分為：
- 原始的快排毁兆。
- 為制造適合高效排序環(huán)境而事先打亂數(shù)組順序的快排。
- 為數(shù)組內(nèi)大量重復(fù)值而優(yōu)化的三向切分快排阴挣。
這里只討論原始的快排气堕。
關(guān)于在快排過程中何時(shí)進(jìn)行交換以及交換誰的問題，我看見兩種不同的思路：
- 當(dāng)左右兩個(gè)游標(biāo)都停止時(shí)畔咧，交換兩個(gè)游標(biāo)所指向元素茎芭。樞軸所在位置暫時(shí)不變，直到兩個(gè)游標(biāo)相遇重合誓沸，才更新樞軸位置梅桩，交換樞軸與游標(biāo)所指元素。
- 當(dāng)右游標(biāo)找到一個(gè)比樞軸小的元素時(shí)拜隧，馬上把樞軸交換到游標(biāo)所在位置摘投，而游標(biāo)位置的元素則移到樞軸那里。完成一次樞軸更新虹蓄。然后左游標(biāo)再去尋找比樞軸大的元素犀呼，同理。
第1種思路可以有效降低交換頻率薇组，在游標(biāo)相遇后再對(duì)樞軸進(jìn)行定位外臂，這步會(huì)導(dǎo)致略微增加了比較的次數(shù)；
第2種思路交換操作會(huì)比較頻繁律胀，但是在交換的過程中同時(shí)也把樞軸的位置不斷進(jìn)行更新宋光，當(dāng)游標(biāo)相遇時(shí)貌矿，樞軸的定位也完成了。
在兩種思路都嘗試實(shí)現(xiàn)過后罪佳，我還是喜歡第2種逛漫，即便交換操作會(huì)多一些，但實(shí)質(zhì)上的交換只是對(duì)數(shù)組特定位置的賦值赘艳，這種操作還是挺快的酌毡。
- 從待排序數(shù)組中選一個(gè)值作為分區(qū)的參考界線，一般選第一個(gè)元素即可蕾管。這個(gè)選出來的值可叫做樞軸
pivot枷踏，它將會(huì)在一趟排序中不斷被移動(dòng)位置，只終移動(dòng)到位于整個(gè)數(shù)組的正確位置上掰曾。 - 一趟排序的目標(biāo)是把小于樞軸的元素放在前方旭蠕，把大于樞軸的元素放在后方，樞軸放在中間旷坦。這看起來一趟排序?qū)嵸|(zhì)上所干的事情就是把數(shù)組分區(qū)掏熬。接下來考慮怎么完成一次分區(qū)。
- 記一個(gè)游標(biāo)
i秒梅，指向待排序數(shù)組的首位旗芬，它將會(huì)不斷向后移動(dòng)；
再記一個(gè)游標(biāo)j番电，指向待排序數(shù)組的末位，它將會(huì)不斷向前移動(dòng)辆琅。
這樣可以預(yù)見的是漱办，i、j終有相遇時(shí)婉烟，當(dāng)它們相遇的時(shí)候娩井，就是這趟排序完成時(shí)。 - 現(xiàn)在讓游標(biāo)
j從后往前掃描似袁，尋找比樞軸小的元素x洞辣，找到后停下來，準(zhǔn)備把這個(gè)元素扔到前方去昙衅。 - 在同一個(gè)數(shù)組內(nèi)排序并不能擴(kuò)大數(shù)組的容量扬霜，那怎么扔呢？
因?yàn)閯偛虐咽孜辉剡x作為pivot而涉，所以當(dāng)前它們的位置關(guān)系是pivot ... x著瓶。
又排序目標(biāo)是升序，x是個(gè)小值卻放在了pivot的后方啼县，不妥材原，需要交換它們的位置沸久。 - 交換完后，它們的位置關(guān)系變成了
x ... pivot余蟹。此時(shí)j指向了pivot卷胯，i指向了x。 - 現(xiàn)在讓游標(biāo)
i向后掃描威酒，尋找比樞軸大的元素y窑睁，找到后停下來，與pivot進(jìn)行交換兼搏。
完成后的位置關(guān)系是pivot ... y卵慰，此時(shí)i指向pivot，即pivot移到了i的位置佛呻。 - 這里有個(gè)小優(yōu)化裳朋，在
i向后掃描開始時(shí)，i是指向x的吓著，而在上一輪j游標(biāo)的掃描中我們已經(jīng)知道x是比pivot小的鲤嫡，所以完全可以讓i跳過x，不需要拿著x和pivot再比較一次绑莺。
結(jié)論是在j游標(biāo)的交換完成后暖眼，順便把i往后移一位，i ++纺裁。
同理诫肠，在i游標(biāo)的交換完成后，順便把j往前移一位欺缘，j --栋豫。 - 在掃描的過程中如果發(fā)現(xiàn)與樞軸相等的元素怎么辦呢？
因我們不討論三向切分的快排優(yōu)化算法谚殊，所以這里答案是：不理它丧鸯。
隨著一趟一趟的排序，它們會(huì)慢慢被更小的元素往后擠嫩絮，被更大的元素往前擠丛肢，最后的結(jié)果就是它們都會(huì)和樞軸一起移到了中間位置。 - 當(dāng)
i和j相遇時(shí)剿干，i和j都會(huì)指向pivot蜂怎。在我們的分區(qū)方法里，把i返回置尔，即在分區(qū)完成后把樞軸位置返回派敷。 - 接下來，讓分出的兩個(gè)數(shù)組分別按上述步驟各自分區(qū)，這是個(gè)遞歸的過程篮愉，直到數(shù)組不能再分時(shí)腐芍，排序完成。
快速排序是很天才的設(shè)計(jì)试躏，實(shí)現(xiàn)不復(fù)雜猪勇，關(guān)鍵是它真的很快~
快速排序.gif
- (void)jx_quickSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
if (self.count == 0) {
return;
}
[self jx_quickSortWithLowIndex:0 highIndex:self.count - 1 usingComparator:comparator didExchange:exchangeCallback];
}
- (void)jx_quickSortWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
if (low >= high) {
return;
}
NSInteger pivotIndex = [self jx_quickPartitionWithLowIndex:low highIndex:high usingComparator:comparator didExchange:exchangeCallback];
[self jx_quickSortWithLowIndex:low highIndex:pivotIndex - 1 usingComparator:comparator didExchange:exchangeCallback];
[self jx_quickSortWithLowIndex:pivotIndex + 1 highIndex:high usingComparator:comparator didExchange:exchangeCallback];
}
- (NSInteger)jx_quickPartitionWithLowIndex:(NSInteger)low highIndex:(NSInteger)high usingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback {
id pivot = self[low];
NSInteger i = low;
NSInteger j = high;
while (i < j) {
// 略過大于等于pivot的元素
while (i < j && comparator(self[j], pivot) != NSOrderedAscending) {
j --;
}
if (i < j) {
// i、j未相遇颠蕴，說明找到了小于pivot的元素泣刹。交換辈赋。
[self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];
i ++;
}
/// 略過小于等于pivot的元素
while (i < j && comparator(self[i], pivot) != NSOrderedDescending) {
i ++;
}
if (i < j) {
// i昆码、j未相遇赴精，說明找到了大于pivot的元素塘揣。交換。
[self jx_exchangeWithIndexA:i indexB:j didExchange:exchangeCallback];
j --;
}
}
return i;
}
UI實(shí)現(xiàn)
現(xiàn)在講下UI的實(shí)現(xiàn)思路采桃。
NSMutableArray+JXSort.h
從前面的排序代碼可以看到况既，我是給NSMutableArray寫了個(gè)分類碍讯，排序邏輯寫在分類里面西轩，完全與視圖無關(guān)员舵。
typedef NSComparisonResult(^JXSortComparator)(id obj1, id obj2);
typedef void(^JXSortExchangeCallback)(id obj1, id obj2);
@interface NSMutableArray (JXSort)
// 選擇排序
- (void)jx_selectionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback;
// 冒泡排序
- (void)jx_bubbleSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback;
// 插入排序
- (void)jx_insertionSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback;
// 快速排序
- (void)jx_quickSortUsingComparator:(JXSortComparator)comparator didExchange:(JXSortExchangeCallback)exchangeCallback;
@end
外部調(diào)用者只需要傳入兩個(gè)參數(shù)：
-
comparator代碼塊。這是遵循蘋果原有API的風(fēng)格設(shè)計(jì)藕畔，在需要比較數(shù)組內(nèi)的兩個(gè)元素時(shí)马僻，排序方法將會(huì)調(diào)用這個(gè)代碼塊，回傳需要比較的兩個(gè)元素給外部調(diào)用者注服，由外部調(diào)用者實(shí)現(xiàn)比較邏輯韭邓，并返回比較結(jié)果給排序方法。 -
exchangeCallback代碼塊溶弟。這個(gè)參數(shù)是實(shí)現(xiàn)視圖變化的關(guān)鍵女淑。排序方法在每次完成兩個(gè)元素的交換時(shí)，都會(huì)調(diào)用這個(gè)代碼塊可很。外部調(diào)用者诗力，比如ViewController就可以知道排序元素每一次變換位置的時(shí)機(jī)凰浮，從而同步視圖的變化我抠。
- (void)jx_exchangeWithIndexA:(NSInteger)indexA indexB:(NSInteger)indexB didExchange:(JXSortExchangeCallback)exchangeCallback {
id temp = self[indexA];
self[indexA] = self[indexB];
self[indexB] = temp;
if (exchangeCallback) {
exchangeCallback(temp, self[indexA]);
}
}
ViewController.m
視圖控制器持有待排序的數(shù)組，這個(gè)數(shù)組是100條細(xì)長(zhǎng)的矩形袜茧，長(zhǎng)度隨機(jī)菜拓。
@property (nonatomic, strong) NSMutableArray<UIView *> *barArray;
由于我們加強(qiáng)了NSMutableArray，它現(xiàn)在可以支持多種指定類型的排序了笛厦，同時(shí)也可以把排序過程反饋給我們纳鼎，當(dāng)需要給barArray排序時(shí)，只需要這樣調(diào)用：
- (void)quickSort {
[self.barArray jx_quickSortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
return [self compareWithBarOne:obj1 andBarTwo:obj2];
} didExchange:^(id obj1, id obj2) {
[self exchangePositionWithBarOne:obj1 andBarTwo:obj2];
}];
}
每一次didExchange的回調(diào)，ViewController都會(huì)對(duì)兩個(gè)視圖的位置進(jìn)行交換贱鄙。如此形成不斷進(jìn)行排序的視覺效果劝贸。
控制排序速度
為了能夠讓肉眼感知排序的過程，我們需要放慢排序的過程逗宁。
這里我的辦法是延長(zhǎng)兩個(gè)元素比較操作的耗時(shí)映九，當(dāng)某個(gè)算法所需要進(jìn)行的比較操作越少時(shí)，它排序就會(huì)越快(根據(jù)上面四張圖的比較瞎颗，毫無疑問快排所進(jìn)行的比較操作是最少啦~)件甥。
那么如何模擬出比較操作的耗時(shí)時(shí)間呢？
這里我的辦法是借助信號(hào)量哼拔，在兩條線程間通訊引有。
1.讓排序在子線程中進(jìn)行，當(dāng)需要進(jìn)行比較操作時(shí)倦逐，阻塞線程譬正，等待信號(hào)的到來。這里的思想是得到一個(gè)信號(hào)才能進(jìn)行一次比較僻孝。
- (NSComparisonResult)compareWithBarOne:(UIView *)barOne andBarTwo:(UIView *)barTwo {
// 模擬進(jìn)行比較所需的耗時(shí)
dispatch_semaphore_wait(self.sema, DISPATCH_TIME_FOREVER);
CGFloat height1 = CGRectGetHeight(barOne.frame);
CGFloat height2 = CGRectGetHeight(barTwo.frame);
if (height1 == height2) {
return NSOrderedSame;
}
return height1 < height2 ? NSOrderedAscending : NSOrderedDescending;
}
2.主線程啟用定時(shí)器导帝，每隔一定時(shí)間發(fā)出一個(gè)信號(hào)，喚醒排序線程穿铆。
self.sema = dispatch_semaphore_create(0);
NSTimeInterval nowTime = [[NSDate date] timeIntervalSince1970];
// 定時(shí)器信號(hào)
__weak typeof(self) weakSelf = self;
self.timer = [NSTimer scheduledTimerWithTimeInterval:0.002 repeats:YES block:^(NSTimer * _Nonnull timer) {
// 發(fā)出信號(hào)量您单，喚醒排序線程
dispatch_semaphore_signal(weakSelf.sema);
// 更新計(jì)時(shí)
NSTimeInterval interval = [[NSDate date] timeIntervalSince1970] - nowTime;
weakSelf.timeLabel.text = [NSString stringWithFormat:@"耗時(shí)(秒):%2.3f", interval];
}];
源碼
https://github.com/JiongXing/JXSort
參考
Swift算法俱樂部中文版 -- 插入排序
算法筆記－排序01:選擇排序,插入排序,希爾排序
算法筆記－排序02:歸并排序,快速排序
1.2-交換排序-快速排序
