各大排序算法的Objective-C實現(xiàn)以及圖形化演示比較是怎樣的

這期內(nèi)容當中小編將會給大家?guī)碛嘘P(guān)各大排序算法的Objective-C實現(xiàn)以及圖形化演示比較是怎樣的，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

用Objective-C實現(xiàn)幾種基本的排序算法，并把排序的過程圖形化顯示。其實算法還是挺有趣的 ^ ^.

• 選擇排序

• 冒泡排序

• 插入排序

• 快速排序

選擇排序

以升序為例。

選擇排序比較好理解，一句話概括就是依次按位置挑選出適合此位置的元素來填充。

1. 暫定***個元素為最小元素，往后遍歷，逐個與最小元素比較，若發(fā)現(xiàn)更小者，與先前的”最小元素”交換位置。達到更新最小元素的目的。

2. 一趟遍歷完成后，能確保剛剛完成的這一趟遍歷中，最的小元素已經(jīng)放置在前方了。然后縮小排序范圍，新一趟排序從數(shù)組的第二個元素開始。

3. 在新一輪排序中重復(fù)第1、2步驟，直到范圍不能縮小為止，排序完成。

選擇排序

以下方法在NSMutableArray+JXSort.m中實現(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];  }  }  }  }

冒泡排序

在一趟遍歷中，不斷地對相鄰的兩個元素進行排序，小的在前大的在后，這樣會造成大值不斷沉底的效果，當一趟遍歷完成時，***的元素會被排在后方正確的位置上。

然后縮小排序范圍，即去掉***方位置正確的元素，對前方數(shù)組進行新一輪遍歷，重復(fù)第1步驟。直到范圍不能縮小為止，排序完成。

- (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];  }  }  }  }

插入排序

插入排序是從一個亂序的數(shù)組中依次取值，插入到一個已經(jīng)排好序的數(shù)組中。

這看起來好像要兩個數(shù)組才能完成，但如果只想在同一個數(shù)組內(nèi)排序，也是可以的。此時需要想象出兩個區(qū)域：前方有序區(qū)和后方亂序區(qū)。

1、分區(qū)。開始時前方有序區(qū)只有一個元素，就是數(shù)組的***個元素。然后把從第二個元素開始直到結(jié)尾的數(shù)組作為亂序區(qū)。

2、從亂序區(qū)取***個元素，把它正確插入到前方有序區(qū)中。把它與前方無序區(qū)的***一個元素比較，亦即與它的前一個元素比較。

• 如果比前一個元素要大，則不需要交換，這時有序區(qū)擴充一格，亂序區(qū)往后縮減一格，相當于直接拼在有序區(qū)末尾。

• 如果和前一個元素相等，則繼續(xù)和前二元素比較、再和前三元素比較……如果往前遍歷到頭了，發(fā)現(xiàn)前方所有元素值都長一個樣的話(囧)，那也可以，不需要交換，這時有序區(qū)擴充一格，亂序區(qū)往后縮減一格，相當于直接拼在有序區(qū)末尾。如果比前一個元素大呢?對不起作為有序區(qū)不可能出現(xiàn)這種情況。如果比前一個元素小呢，請看下一點。

• 如果比前一個元素小，則交換它們的位置。交換完后，繼續(xù)比較取出元素和它此時的前一個元素，若更小就交換，若相等就比較前一個，直到遍歷完成。至此，把亂序區(qū)***個元素正確插入到前方有序區(qū)中。

3、往后縮小亂序區(qū)范圍，繼續(xù)取縮小范圍后的***個元素，重復(fù)第2步驟。直到范圍不能縮小為止，排序完成。

- (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];  }  }  }

快速排序

快排的版本有好幾種，粗略可分為：

1. 原始的快排。

2. 為制造適合高效排序環(huán)境而事先打亂數(shù)組順序的快排。

3. 為數(shù)組內(nèi)大量重復(fù)值而優(yōu)化的三向切分快排。

這里只討論原始的快排。

關(guān)于在快排過程中何時進行交換以及交換誰的問題，我看見兩種不同的思路：

1. 當左右兩個游標都停止時，交換兩個游標所指向元素。樞軸所在位置暫時不變，直到兩個游標相遇重合，才更新樞軸位置，交換樞軸與游標所指元素。

2. 當右游標找到一個比樞軸小的元素時，馬上把樞軸交換到游標所在位置，而游標位置的元素則移到樞軸那里。完成一次樞軸更新。然后左游標再去尋找比樞軸大的元素，同理。

第1種思路可以有效降低交換頻率，在游標相遇后再對樞軸進行定位，這步會導(dǎo)致略微增加了比較的次數(shù);

第2種思路交換操作會比較頻繁，但是在交換的過程中同時也把樞軸的位置不斷進行更新，當游標相遇時，樞軸的定位也完成了。

在兩種思路都嘗試實現(xiàn)過后，我還是喜歡第2種，即便交換操作會多一些，但實質(zhì)上的交換只是對數(shù)組特定位置的賦值，這種操作還是挺快的。

1. 從待排序數(shù)組中選一個值作為分區(qū)的參考界線，一般選***個元素即可。這個選出來的值可叫做樞軸pivot，它將會在一趟排序中不斷被移動位置，只終移動到位于整個數(shù)組的正確位置上。

2. 一趟排序的目標是把小于樞軸的元素放在前方，把大于樞軸的元素放在后方，樞軸放在中間。這看起來一趟排序?qū)嵸|(zhì)上所干的事情就是把數(shù)組分區(qū)。接下來考慮怎么完成一次分區(qū)。

3. 記一個游標i，指向待排序數(shù)組的首位，它將會不斷向后移動;
   再記一個游標j，指向待排序數(shù)組的末位，它將會不斷向前移動。
   這樣可以預(yù)見的是，i 、j終有相遇時，當它們相遇的時候，就是這趟排序完成時。

4. 現(xiàn)在讓游標j從后往前掃描，尋找比樞軸小的元素x，找到后停下來，準備把這個元素扔到前方去。

5. 在同一個數(shù)組內(nèi)排序并不能擴大數(shù)組的容量，那怎么扔呢?
   因為剛才把首位元素選作為pivot，所以當前它們的位置關(guān)系是pivot ... x。
   又排序目標是升序，x是個小值卻放在了pivot的后方，不妥，需要交換它們的位置。

6. 交換完后，它們的位置關(guān)系變成了x ... pivot。此時j指向了pivot，i指向了x。

7. 現(xiàn)在讓游標i向后掃描，尋找比樞軸大的元素y，找到后停下來，與pivot進行交換。
   完成后的位置關(guān)系是pivot ... y，此時i指向pivot，即pivot移到了i的位置。

8. 這里有個小優(yōu)化，在i向后掃描開始時，i是指向x的，而在上一輪j游標的掃描中我們已經(jīng)知道x是比pivot小的，所以完全可以讓i跳過x，不需要拿著x和pivot再比較一次。
   結(jié)論是在j游標的交換完成后，順便把i往后移一位，i ++。
   同理，在i游標的交換完成后，順便把j往前移一位，j --。

9. 在掃描的過程中如果發(fā)現(xiàn)與樞軸相等的元素怎么辦呢?
   因我們不討論三向切分的快排優(yōu)化算法，所以這里答案是：不理它。
   隨著一趟一趟的排序，它們會慢慢被更小的元素往后擠，被更大的元素往前擠，***的結(jié)果就是它們都會和樞軸一起移到了中間位置。

10. 當i和j相遇時，i和j都會指向pivot。在我們的分區(qū)方法里，把i返回，即在分區(qū)完成后把樞軸位置返回。

11. 接下來，讓分出的兩個數(shù)組分別按上述步驟各自分區(qū)，這是個遞歸的過程，直到數(shù)組不能再分時，排序完成。

快速排序是很天才的設(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實現(xiàn)

現(xiàn)在講下UI的實現(xiàn)思路。

NSMutableArray+JXSort.h

從前面的排序代碼可以看到，我是給NSMutableArray寫了個分類，排序邏輯寫在分類里面，完全與視圖無關(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)用者只需要傳入兩個參數(shù)：

• comparator代碼塊。這是遵循蘋果原有API的風(fēng)格設(shè)計，在需要比較數(shù)組內(nèi)的兩個元素時，排序方法將會調(diào)用這個代碼塊，回傳需要比較的兩個元素給外部調(diào)用者，由外部調(diào)用者實現(xiàn)比較邏輯，并返回比較結(jié)果給排序方法。

• exchangeCallback代碼塊。這個參數(shù)是實現(xiàn)視圖變化的關(guān)鍵。排序方法在每次完成兩個元素的交換時，都會調(diào)用這個代碼塊。外部調(diào)用者，比如ViewController就可以知道排序元素每一次變換位置的時機，從而同步視圖的變化。

- (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ù)組，這個數(shù)組是100條細長的矩形，長度隨機。

@property (nonatomic, strong) NSMutableArray *barArray;

由于我們加強了NSMutableArray，它現(xiàn)在可以支持多種指定類型的排序了，同時也可以把排序過程反饋給我們，當需要給barArray排序時，只需要這樣調(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都會對兩個視圖的位置進行交換。如此形成不斷進行排序的視覺效果。

控制排序速度

為了能夠讓肉眼感知排序的過程，我們需要放慢排序的過程。

這里我的辦法是延長兩個元素比較操作的耗時，大約延長到0.002秒。結(jié)果很明顯，當某個算法所需要進行的比較操作越少時，它排序就會越快(根據(jù)上面四張圖的比較，毫無疑問快排所進行的比較操作是最少啦~)。

那么如何模擬出比較操作的耗時時間呢?

這里我的辦法是借助信號量，在兩條線程間通訊。

1.讓排序在子線程中進行，當需要進行比較操作時，阻塞線程，等待信號的到來。這里的思想是得到一個信號才能進行一次比較。

- (NSComparisonResult)compareWithBarOne:(UIView *)barOne andBarTwo:(UIView *)barTwo {  // 模擬進行比較所需的耗時  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.主線程啟用定時器，每隔0.002秒發(fā)出一個信號，喚醒排序線程。

self.sema = dispatch_semaphore_create(0);  NSTimeInterval nowTime = [[NSDate date] timeIntervalSince1970];  // 定時器信號  __weak typeof(self) weakSelf = self;  self.timer = [NSTimer scheduledTimerWithTimeInterval:0.002 repeats:YES block:^(NSTimer * _Nonnull timer) {  // 發(fā)出信號量，喚醒排序線程  dispatch_semaphore_signal(weakSelf.sema);  // 更新計時  NSTimeInterval interval = [[NSDate date] timeIntervalSince1970] - nowTime;  weakSelf.timeLabel.text = [NSString stringWithFormat:@"耗時(秒):%2.3f", interval];  }];

上述就是小編為大家分享的各大排序算法的Objective-C實現(xiàn)以及圖形化演示比較是怎樣的了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道。