排序
冒泡排序 Bubble Sort
比较相邻的两个元素，如果第一个比第二个大，则交换它们。一遍排序后，最大的元素会“冒泡”到数组的末尾。然后重复这个过程，每次不包括已排序的部分，直到整个数组都被排序。时间复杂度为O(n^2)，是稳定的排序算法。
优点：
- 实现简单，容易理解和实现。
- 稳定，相邻的两个元素比较时不会改变它们的相对位置。
缺点：
- 时间复杂度较高，平均情况下需要O(n^2)的比较和交换次数。
- 对于大规模数据排序较慢。
OC演示代码
- (NSArray *)bubbleSort:(NSArray *)unsortedArray {
NSMutableArray *array = [NSMutableArray arrayWithArray:unsortedArray];
NSUInteger n = [array count];
for (NSUInteger i = 0; i < n - 1; i++) {
for (NSUInteger j = 0; j < n - i - 1; j++) {
if ([array[j] compare:array[j+1]] == NSOrderedDescending) {
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
return [NSArray arrayWithArray:array];
}
NSArray *unsortedArray = @[@3, @1, @4, @1, @5, @9, @2, @6, @5, @3, @5];
NSArray *sortedArray = [self bubbleSort:unsortedArray];
NSLog(@"冒泡排序结果：%@", sortedArray);
//冒泡排序结果：(1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9)
python演示代码
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
unsorted_arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = bubble_sort(unsorted_arr)
print("冒泡排序结果：", sorted_arr)
#冒泡排序结果： [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]
选择排序 Selection Sort
从未排序的元素中选出最小的元素，将它放到已排序的序列的末尾。重复这个过程，直到整个数组都被排序。时间复杂度为O(n^2)，是不稳定的排序算法。
优点：
- 实现简单，容易理解和实现。
- 不占用额外的内存空间。
- 交换次数比冒泡排序少，性能比冒泡排序要好。
缺点：
- 时间复杂度较高，平均情况下需要O(n^2)的比较和交换次数。
- 不稳定，有可能改变相同元素的相对位置。
插入排序 Insertion Sort
将未排序的元素插入到已排序序列中的适当位置，以使得插入后序列仍然有序。时间复杂度为O(n^2)，是稳定的排序算法。
优点：
- 对于小规模数据排序性能较好。
- 稳定，相同元素的相对位置不会改变。
- 算法稳定，且可以用链表实现。
缺点：
- 时间复杂度较高，平均情况下需要O(n^2)的比较和交换次数。
- 对于大规模数据排序较慢。
希尔排序 Shell Sort
基于插入排序，将数组分成若干子序列进行插入排序，逐渐缩小子序列的长度，直到子序列长度为1。时间复杂度最好为O(nlogn)，最坏为O(n^2)，是不稳定的排序算法。
优点：
- 在一定程度上提高了插入排序的效率，特别是对于中等规模的数据集合。
- 可以根据数据的分布情况选择不同的步长，从而更加高效。
缺点：
- 不稳定，有可能改变相同元素的相对位置。
- 选取合适的步长是个难题。
归并排序 Merge Sort
将数组分成两个部分，分别对每个部分进行排序，然后将它们合并到一起。重复这个过程，直到整个数组都被排序。时间复杂度为O(nlogn)，是稳定的排序算法。
优点：
- 时间复杂度为O(nlogn)，比较稳定。
- 稳定，相同元素的相对位置不会改变。
缺点：
- 空间复杂度较高，需要额外的O(n)的空间。
- 归并操作的常数比较大。
快速排序 Quick Sort
选择一个基准元素，将数组分成比基准元素小的部分和比基准元素大的部分，然后递归地对这两个部分进行快速排序。时间复杂度最好为O(nlogn)，最坏为O(n^2)，是不稳定的排序算法。
优点：
- 时间复杂度最好情况下为O(nlogn)，比较快。
- 不占用额外的内存空间。
- 可以轻易地修改为不同的分区策略，适用于不同的数据分布情况。
缺点：
- 在最坏情况下，时间复杂度可以退化为O(n^2)，此时需要选择更好的分区策略。
- 不稳定，有可能改变相同元素的相对位置。
堆排序 Heap Sort
将数组转换成一个最大堆（或最小堆），然后从堆顶开始依次取出元素，放到已排序的序列中。重复这个过程，直到整个数组都被排序。时间复杂度为O(nlogn)，是不稳定的排序算法。
