OC版八大经典排序算法

总结一下八大经典排序算法!

冒泡排序
- (NSMutableArray *)bubbleSort:(NSMutableArray *)array
{
    for (NSInteger i = 0 ; i < array.count ; i ++ )
    {
        for (NSInteger j = 0 ; j < i ; j ++ )
        {
            if (array[i] < array[j])
            {
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
    return array.copy;
}
选择排序
- (NSMutableArray *)selectSort:(NSMutableArray *)array
{
    for (NSInteger i = 0 ; i < array.count ; i ++ )
    {
        for (NSInteger j = i + 1 ; j < array.count ; j ++ )
        {
            if (array[i] > array[j])
            {
                [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
        }
    }
    return array.copy;
}
插入排序
- (NSMutableArray *)insertSort:(NSMutableArray *)array
{
    for (NSInteger i = 0 ; i < array.count ; i ++ )
    {
        NSNumber * temp = array[i];
        for (NSInteger j = i - 1 ; j >= 0 && temp < array[j] ; j -- )
        {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
        }
    }
    return array.copy;
}
快速排序
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
- (NSMutableArray *)quicklySort:(NSMutableArray *)array
{
[self quickSort:array leftIndex:0 rightIndex:array.count - 1];
return array.copy;
}
- (void)quickSort:(NSMutableArray *)array leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
if (left < right)
{
NSInteger temp = [self getMiddleIndex:array leftIndex:left rightIndex:right];
[self quickSort:array leftIndex:left rightIndex:temp - 1];
[self quickSort:array leftIndex:temp + 1 rightIndex:right];
}
}
- (NSInteger)getMiddleIndex:(NSMutableArray *)array leftIndex:(NSInteger)left rightIndex:(NSInteger)right
{
NSNumber * temp = array[left];
while (left < right) {
while (left < right && temp <= array[right]) {
right -- ;
}
if (left < right)
{
array[left] = array[right];
}
while (left < right && array[left] <= temp) {
left ++ ;
}
if (left < right)
{
array[right] = array[left];
}
}
array[left] = temp;
return left;
}
希尔排序
- (NSMutableArray *)shellSort:(NSMutableArray *)array
{
    for (NSInteger increment = array.count / 2 ; increment > 0 ; increment /= 2 )
    {
        for (NSInteger i = increment ; i < array.count ; i ++ )
        {
            NSInteger j = i ;
            for (; j - increment >= 0 && array[j] < array[j-increment]; j -= increment)
            {
                [array exchangeObjectAtIndex:j withObjectAtIndex:(j - increment)];
            }
        }
    }
    return array.copy;
}
归并排序
- (NSMutableArray *)megerSortAscendingOrderSort:(NSMutableArray *)ascendingArr
{
    //tempArray数组里存放ascendingArr个数组,每个数组包含一个元素
    NSMutableArray *tempArray = [NSMutableArray arrayWithCapacity:1];
    for (NSNumber *num in ascendingArr) {
        NSMutableArray *subArray = [NSMutableArray array];
        [subArray addObject:num];
        [tempArray addObject:subArray];
    }
    //开始合并为一个数组
    while (tempArray.count != 1) {
        NSInteger i = 0;
        while (i < tempArray.count - 1) {
            tempArray[i] = [self mergeArrayFirstList:tempArray[i] secondList:tempArray[i + 1]];
            [tempArray removeObjectAtIndex:i + 1];
            i++;
        }
    }
    NSLog(@"归并升序排序结果:%@", tempArray[0]);
    return tempArray[0];
}

- (NSArray *)mergeArrayFirstList:(NSArray *)array1 secondList:(NSArray *)array2 {
    NSMutableArray *resultArray = [NSMutableArray array];
    NSInteger firstIndex = 0, secondIndex = 0;
    while (firstIndex < array1.count && secondIndex < array2.count) {
        if ([array1[firstIndex] floatValue] < [array2[secondIndex] floatValue]) {
            [resultArray addObject:array1[firstIndex]];
            firstIndex++;
        } else {
            [resultArray addObject:array2[secondIndex]];
            secondIndex++;
        }
    }
    while (firstIndex < array1.count) {
        [resultArray addObject:array1[firstIndex]];
        firstIndex++;
    }
    while (secondIndex < array2.count) {
        [resultArray addObject:array2[secondIndex]];
        secondIndex++;
    }
    return resultArray.copy;
}
堆排序
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
- (NSMutableArray *)heapSortArray:(NSMutableArray *)array
{
return [self heapSort:array];
}

- (NSMutableArray *)heapSort:(NSMutableArray *)array
{
NSMutableArray * list = [NSMutableArray arrayWithArray:array];
NSInteger endIndex = array.count - 1;
//创建大顶堆 把array 转换为大顶堆层次的遍历结果
[self heapCreate:list];
while (endIndex >= 0) {
//交换大顶堆的收尾两个值
[list exchangeObjectAtIndex:0 withObjectAtIndex:endIndex];
//缩小大顶堆的范围
endIndex -- ;
[self heapAdjast:list withStartIndex:0 withEndIndex:endIndex + 1];
}
return list;
}

//构建大顶堆的层次遍历序列
- (void)heapCreate:(NSMutableArray *)array
{
NSInteger i = array.count;
for (; i > 0; i -- )
{
[self heapAdjast:array withStartIndex:i - 1 withEndIndex:array.count];
}
}
//对大顶堆的局部调整,使其改节点的所有父类符合大顶堆的特点
- (void)heapAdjast:(NSMutableArray *)array withStartIndex:(NSInteger)startIndex withEndIndex:(NSInteger)endIndex
{
NSNumber * temp = array[startIndex];
//父节点下标
NSInteger fatherIndex = startIndex + 1;
//左孩子下标
NSInteger leftChildIndex = fatherIndex * 2;
while (leftChildIndex <= endIndex) {
//比较左右节点 找出较大的角标
if (leftChildIndex < endIndex && array[leftChildIndex - 1] < array[leftChildIndex])
{
leftChildIndex ++ ;
}

//如果较大的子节点比根节点大 赋值为父节点
if (temp < array[leftChildIndex - 1])
{
array[fatherIndex - 1] = array[leftChildIndex - 1];
}
else
{
break ;
}

fatherIndex = leftChildIndex;
leftChildIndex = fatherIndex * 2;
}
array[fatherIndex - 1] = temp;
}
基数排序
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
- (NSMutableArray *)radixSortArray:(NSMutableArray *)array
{
[self radixSort:array];
return array.copy;
}

- (void)radixSort:(NSMutableArray *)array
{
//创建空桶
NSMutableArray * bucket = [self createBucket];

//待排数组的最大数值
NSNumber * maxNumber = [self listMaxItem:array];

//最大数值的数字位数
NSInteger maxLength = [self numberLength:maxNumber];

//按照从低位到高位的顺序执行排序过程
for (NSInteger digit = 1 ; digit <= maxLength ; digit ++ )
{
//入桶
for (NSNumber * item in array)
{
//确定item 归属哪个桶 以digit位数为基数
NSInteger baseNumber = [self fetchBaseNumber:item digit:digit];
NSMutableArray * mutArray = bucket[baseNumber];
//将数据放入空桶上
[mutArray addObject:item];
}

NSInteger index = 0;

//出桶
for (NSInteger i = 0 ; i < bucket.count ; i ++ )
{
NSMutableArray * subArray = bucket[i];
//将桶的数据放回待排数组中
while (subArray.count != 0) {
NSNumber * number = [subArray objectAtIndex:0];
array[index] = number;
[subArray removeObjectAtIndex:0];
index ++ ;
}
}
}
}

//创建空桶
- (NSMutableArray *)createBucket
{
NSMutableArray * bucket = [NSMutableArray array];
for (NSInteger i = 0 ; i < 10 ; i ++ )
{
NSMutableArray * array = [NSMutableArray array];
[bucket addObject:array];
}
return bucket;
}

//取列表最大值
- (NSNumber *)listMaxItem:(NSArray *)array
{
NSNumber * maxNumber = array[0];
for (NSNumber * number in array)
{
if (maxNumber < number)
{
maxNumber = number;
}
}
return maxNumber;
}

//数字的位数
- (NSInteger)numberLength:(NSNumber *)number
{
NSString * string = [NSString stringWithFormat:@"%ld",(long)[number integerValue]];
return string.length;
}

//number 操作的数字 digit 位数 返回该位数上的数字
- (NSInteger)fetchBaseNumber:(NSNumber *)number digit:(NSInteger)digit
{
//digit为基数位数
if (digit > 0 && digit <= [self numberLength:number])
{
NSMutableArray * numbersArray = [NSMutableArray array];
NSString * string = [NSString stringWithFormat:@"%ld",[number integerValue]];
for (NSInteger index = 0 ; index < [self numberLength:number] ; index ++ )
{
NSString * temp = [string substringWithRange:NSMakeRange(index, 1)];
[numbersArray addObject:temp];
}
NSString * str = numbersArray[numbersArray.count - digit];
return [str integerValue];
}
return 0;
}
-------------本文结束感谢您的阅读-------------
枫林飘雪 wechat
欢迎您扫一扫上面的微信订阅号,订阅我的博客!
坚持技术分享,您的支持将鼓励我继续创作!