快速排序的几种方式
首先需要创建交换数组中元素的方法
//交换数组中的两个数- (void)swap:(NSMutableArray *)sourceArr numI:(int)i numJ:(int)j{ NSNumber *temp; temp = sourceArr[i]; sourceArr[i] = sourceArr[j]; sourceArr[j] = temp;}复制代码 快速排序方法一
//快速排序(基本的思想就是，i指向最左边元素的下一个元素，j指向最后一个元素，然后从右向左寻找第一个比中轴元素小的元素，从左向右寻找一个比中轴元素大的元素，两者交换位置，当i>j的时候，交换中轴元素和j的位置，最后通过递归对中轴前后的元素分别进行递归)- (void)quickSort:(NSMutableArray *)sourceArr indexL:(int)indexL indexR:(int)indexR{ //递归的边界条件 if (indexL < indexR) { //获取最左边的元素作为中轴元素 int pio = [sourceArr[indexL] intValue]; int i = indexL + 1; int j = indexR; while (i <= j) { //先从右往左查找 while (i <= j && [sourceArr[j] intValue] > pio) { j--; } //从左往右查找 while (i <= j && [sourceArr[i] intValue] <= pio) { i++; } if (i < j) { //交换两个数 [self swap:sourceArr numI:i numJ:j]; i++; j--; } } //最后一次将j的位置的元素与中轴元素进行交换 [self swap:sourceArr numI:indexL numJ:j]; //递归调用，对左边元素按相同的方式依次进行排序 [self quickSort:sourceArr indexL:indexL indexR:j - 1]; //递归调用，对右边元素按相同的方式依次进行排序 [self quickSort:sourceArr indexL:j + 1 indexR:indexR]; }}复制代码 快速排序方法二
//快速排序方法2（将最左边的元素作为中轴元素，先从后往前查找出当前比中轴元素小的元素，交换两者位置，然后从前往后查找出比当前中轴元素大的元素，交换两者位置，直到i和j相等，此处就是最终中轴的位置，然后对中轴前后的元素分别进行递归）- (void)quickSort2:(NSMutableArray *)sourceArr indexL:(int)indexL indexR:(int)indexR{ //递归的边界 if (indexL < indexR) { //获取中轴元素 int pio = [sourceArr[indexL] intValue]; int i = indexL; int j = indexR; while (i < j) { //从后往前查找小于中轴元素的元素 while (i < j && [sourceArr[j] intValue] > pio) { j--; } //将j位置的元素赋值给i sourceArr[i] = sourceArr[j]; //从前往后查找大于中轴元素的元素 while (i < j && [sourceArr[i] intValue] <= pio) { i++; } //将i位置的元素赋值给j sourceArr[j] = sourceArr[i]; } //当i和j指向同一个位置的时候，将中轴元素的值赋值给i sourceArr[i] = @(pio); //递归遍历 [self quickSort2:sourceArr indexL:indexL indexR:i - 1]; [self quickSort2:sourceArr indexL:i + 1 indexR:indexR]; }}复制代码 快速排序方法三
//快速排序方法3（将最左边的元素作为中轴元素，将i指向中轴元素，j指向中轴元素的下一个未知元素，判断j指向的元素是否比中轴元素小，如果小，则将i++,然后交换j和i元素的位置，如果大于，则j向后移动一位）- (void)quickSort3:(NSMutableArray *)sourceArr indexL:(int)indexL indexR:(int)indexR{ if (indexL < indexR) { //获取中轴元素 int pio = [sourceArr[indexL] intValue]; int i = indexL; int j = indexL + 1; while (j <= indexR) { //判断j位置的元素的大小 if ([sourceArr[j] intValue] <= pio) { i++; //交换i和j [self swap:sourceArr numI:i numJ:j]; j++; }else{ j++; } } //交换i和中轴元素的位置，将中轴元素放在指定的位置上 [self swap:sourceArr numI:indexL numJ:i]; //递归左边的数据 [self quickSort3:sourceArr indexL:indexL indexR:i - 1]; [self quickSort3:sourceArr indexL:i + 1 indexR:indexR]; }}复制代码 快速排序方法四
//快速排序算法4（定义一个cur和pre，cur指向最左边的位置，pre指向cur的前一个位置，key表示最后一个位置，cur和pre同时往前走，当遇见cur的值比key大时，cur和pre之间的距离会拉大，当cur的值比key小时，交换cur和pre的位置，然后继续往后移动，当cur移动到key的位置时，交换pre和key的位置）- (void)quickSort4:(NSMutableArray *)sourceArr indexL:(int)indexL indexR:(int)indexR{ if (indexL < indexR) { int key = [sourceArr[indexR] intValue]; int cur = indexL; int pre = cur - 1; while (cur < indexR) { //如果找到小于key的值，并且cur和pre之间有距离的时候 while ([sourceArr[cur] intValue] < key && ++pre != cur) { //交换pre和cur的数据 [self swap:sourceArr numI:cur numJ:pre]; } ++cur; } [self swap:sourceArr numI:++pre numJ:indexR]; //递归前一部分和后一部分的数据 [self quickSort4:sourceArr indexL:indexL indexR:pre - 1]; [self quickSort4:sourceArr indexL:pre + 1 indexR:indexR]; }}复制代码 冒泡排序
//冒泡排序，比较相邻的两个元素- (void)bubblingSort:(NSMutableArray *)sourceArr{ for (int i = 0; i < sourceArr.count - 1; i++) { for (int j = 0; j < sourceArr.count - i - 1; j++) { if ([sourceArr[j] intValue] > [sourceArr[j + 1] intValue]) { [self swap:sourceArr numI:j numJ:j + 1]; } } }}复制代码