Objective C 语言 实现列表排序

Objective-C阿木 发布于 18 天前 3 次阅读


摘要:在Objective-C编程中,列表排序是一个常见且重要的操作。本文将围绕Objective-C语言实现列表排序这一主题,详细介绍几种常用的排序算法,并通过实际代码示例展示如何在Objective-C中实现这些排序算法。

一、

在Objective-C编程中,列表(Array)是常用的数据结构之一。对列表进行排序是数据处理的基本操作,也是编程中常见的需求。本文将介绍几种在Objective-C中实现列表排序的方法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序等。

二、冒泡排序

冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行,直到没有再需要交换的元素为止。

以下是使用Objective-C实现冒泡排序的代码示例:

objective-c

import <Foundation/Foundation.h>

NSArray bubbleSort(NSArray array) {


NSMutableArray sortedArray = [NSMutableArray arrayWithArray:array];


NSUInteger length = [sortedArray count];


for (NSUInteger i = 0; i < length - 1; i++) {


for (NSUInteger j = 0; j < length - i - 1; j++) {


if ([sortedArray[j] compare:sortedArray[j + 1]] == NSOrderedDescending) {


[sortedArray exchangeObjectAtIndex:j withObjectAtIndex:j + 1];


}


}


}


return sortedArray;


}

int main(int argc, const char argv[]) {


@autoreleasepool {


NSArray numbers = @[@3, @2, @5, @1, @4];


NSArray sortedNumbers = bubbleSort(numbers);


NSLog(@"Sorted Numbers: %@", sortedNumbers);


}


return 0;


}


三、选择排序

选择排序是一种简单直观的排序算法。它的工作原理是:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

以下是使用Objective-C实现选择排序的代码示例:

objective-c

NSArray selectionSort(NSArray array) {


NSMutableArray sortedArray = [NSMutableArray arrayWithArray:array];


NSUInteger length = [sortedArray count];


for (NSUInteger i = 0; i < length - 1; i++) {


NSUInteger minIndex = i;


for (NSUInteger j = i + 1; j < length; j++) {


if ([sortedArray[j] compare:sortedArray[minIndex]] == NSOrderedAscending) {


minIndex = j;


}


}


[sortedArray exchangeObjectAtIndex:i withObjectAtIndex:minIndex];


}


return sortedArray;


}

int main(int argc, const char argv[]) {


@autoreleasepool {


NSArray numbers = @[@3, @2, @5, @1, @4];


NSArray sortedNumbers = selectionSort(numbers);


NSLog(@"Sorted Numbers: %@", sortedNumbers);


}


return 0;


}


四、插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序)。

以下是使用Objective-C实现插入排序的代码示例:

objective-c

NSArray insertionSort(NSArray array) {


NSMutableArray sortedArray = [NSMutableArray arrayWithArray:array];


NSUInteger length = [sortedArray count];


for (NSUInteger i = 1; i < length; i++) {


id key = sortedArray[i];


NSUInteger j = i - 1;


while (j >= 0 && [sortedArray[j] compare:key] == NSOrderedDescending) {


[sortedArray replaceObjectAtIndex:j + 1 withObject:key];


j--;


}


[sortedArray replaceObjectAtIndex:j + 1 withObject:key];


}


return sortedArray;


}

int main(int argc, const char argv[]) {


@autoreleasepool {


NSArray numbers = @[@3, @2, @5, @1, @4];


NSArray sortedNumbers = insertionSort(numbers);


NSLog(@"Sorted Numbers: %@", sortedNumbers);


}


return 0;


}


五、快速排序

快速排序是一种分而治之的排序算法。它将原始数组分为较小的两个子数组,然后递归地对这两个子数组进行排序。

以下是使用Objective-C实现快速排序的代码示例:

objective-c

NSArray quickSort(NSArray array) {


if ([array count] <= 1) {


return array;


}



id pivot = [array objectAtIndex:0];


NSArray less = [array subarrayWithRange:NSMakeRange(1, [array count] - 1)];


NSArray greater = [quickSort([less filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"$@ < %@", pivot]])];


NSArray equal = [array filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"$@ == %@", pivot]];



return [greater arrayByAddingObject:pivot];


}

int main(int argc, const char argv[]) {


@autoreleasepool {


NSArray numbers = @[@3, @2, @5, @1, @4];


NSArray sortedNumbers = quickSort(numbers);


NSLog(@"Sorted Numbers: %@", sortedNumbers);


}


return 0;


}


六、归并排序

归并排序是一种分而治之的排序算法。它将原始数组分为两个子数组,然后递归地对这两个子数组进行排序,最后将两个已排序的子数组合并成一个有序数组。

以下是使用Objective-C实现归并排序的代码示例:

objective-c

NSArray merge(NSArray left, NSArray right) {


NSMutableArray result = [NSMutableArray array];


NSUInteger leftIndex = 0, rightIndex = 0;



while (leftIndex < [left count] && rightIndex < [right count]) {


if ([left[leftIndex] compare:right[rightIndex]] == NSOrderedAscending) {


[result addObject:left[leftIndex]];


leftIndex++;


} else {


[result addObject:right[rightIndex]];


rightIndex++;


}


}



while (leftIndex < [left count]) {


[result addObject:left[leftIndex]];


leftIndex++;


}



while (rightIndex < [right count]) {


[result addObject:right[rightIndex]];


rightIndex++;


}



return result;


}

NSArray mergeSort(NSArray array) {


if ([array count] <= 1) {


return array;


}



NSUInteger middle = [array count] / 2;


NSArray left = [array subarrayWithRange:NSMakeRange(0, middle)];


NSArray right = [array subarrayWithRange:NSMakeRange(middle, [array count] - middle)];



NSArray sortedLeft = mergeSort(left);


NSArray sortedRight = mergeSort(right);



return merge(sortedLeft, sortedRight);


}

int main(int argc, const char argv[]) {


@autoreleasepool {


NSArray numbers = @[@3, @2, @5, @1, @4];


NSArray sortedNumbers = mergeSort(numbers);


NSLog(@"Sorted Numbers: %@", sortedNumbers);


}


return 0;


}


七、总结

本文介绍了在Objective-C语言中实现列表排序的几种常用算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。通过实际代码示例,展示了如何在Objective-C中实现这些排序算法。在实际应用中,可以根据具体需求和数据特点选择合适的排序算法,以达到最佳的性能和效率。