iOS-快速算法

亦凉 2023-10-17 14:10 9阅读 0赞

设要排序的数组是**mutableArray**对象，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一次快速排序。

**步骤讲解**

1 ）.设置两个变量**i**，**j** ，排序开始时**i** =  **0**，就**j = mutableArray.count - 1**；

2 ）.设置数组的第一个值为比较基准数**key**，**key** = **mutableArray.count\[0\]**；

3 ）.因为设置**key**为数组的第一个值，所以先从数组最右边开始往前查找比**key**小的值。如果没有找到，**j--**继续往前搜索；如果找到则将**mutableArray\[i\]**和**mutableArray\[j\]**互换，并且停止往前搜索，进入第**4**步；

4 ）.从**i**位置开始往后搜索比可以大的值，如果没有找到，**i**\++继续往后搜索；如果找到则将**mutableArray\[i\]**和**mutableArray\[j\]**互换，并且停止往后搜索；

5 ）.重复第**3**、**4**步，直到**i** == **j**（此时刚好执行完第三步或第四部），停止排序；

**OC代码实现**

<table> 
 <tbody> 
 <tr> 
 <td> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 </td> 
 <td> <code>-&nbsp;(void)viewDidLoad&nbsp;{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>[</code><code>super</code>&nbsp;<code>viewDidLoad];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>NSMutableArray&nbsp;*arr&nbsp;=&nbsp;[[NSMutableArray&nbsp;alloc]&nbsp;initWithObjects:@(6),&nbsp;@(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>[self&nbsp;quickSortArray:arr&nbsp;withLeftIndex:0&nbsp;andRightIndex:arr.count&nbsp;-&nbsp;1];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>NSLog(@</code><code>"%@"</code><code>,arr);</code> <code>}</code> <code>-&nbsp;(void)quickSortArray:(NSMutableArray&nbsp;*)array&nbsp;withLeftIndex:(NSInteger)leftIndex&nbsp;andRightIndex:(NSInteger)rightIndex</code> <code>{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code>&nbsp;<code>(leftIndex&nbsp;&gt;=&nbsp;rightIndex)&nbsp;{ </code><code>//如果数组长度为0或1时返回</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code>&nbsp;<code>;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>NSInteger&nbsp;i&nbsp;=&nbsp;leftIndex;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>NSInteger&nbsp;j&nbsp;=&nbsp;rightIndex;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//记录比较基准数</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>NSInteger&nbsp;key&nbsp;=&nbsp;[array[i]&nbsp;integerValue];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code>&nbsp;<code>(i&nbsp;&lt;&nbsp;j)&nbsp;{ </code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/****&nbsp;首先从右边j开始查找比基准数小的值&nbsp;***/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code>&nbsp;<code>(i&nbsp;&lt;&nbsp;j&nbsp;&amp;&amp;&nbsp;[array[j]&nbsp;integerValue]&nbsp;&gt;=&nbsp;key)&nbsp;{ </code><code>//如果比基准数大，继续查找</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>j--;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//如果比基准数小，则将查找到的小值调换到i的位置</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>array[i]&nbsp;=&nbsp;array[j];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/****&nbsp;当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值&nbsp;***/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code>&nbsp;<code>(i&nbsp;&lt;&nbsp;j&nbsp;&amp;&amp;&nbsp;[array[i]&nbsp;integerValue]&nbsp;&lt;=&nbsp;key)&nbsp;{ </code><code>//如果比基准数小，继续查找</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>i++;</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//如果比基准数大，则将查找到的大值调换到j的位置</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>array[j]&nbsp;=&nbsp;array[i];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>}</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//将基准数放到正确位置</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>array[i]&nbsp;=&nbsp;@(key);</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>/****&nbsp;递归排序&nbsp;***/</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//排序基准数左边的</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>[self&nbsp;quickSortArray:array&nbsp;withLeftIndex:leftIndex&nbsp;andRightIndex:i&nbsp;-&nbsp;1];</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>//排序基准数右边的</code> <code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>[self&nbsp;quickSortArray:array&nbsp;withLeftIndex:i&nbsp;+&nbsp;1&nbsp;andRightIndex:rightIndex];</code> <code>}</code> </td> 
 </tr> 
 </tbody> 
</table>