iOS面试常考算法解析：冒泡排序与选择排序

"这篇文章主要介绍了iOS面试中常遇到的几种排序算法，包括冒泡排序和选择排序，并给出了相应的代码实现。此外，还提及了快速排序算法的起点，但未给出完整实现。" 在iOS面试中，掌握基础的算法是至关重要的，特别是排序算法，因为它们在实际开发中有着广泛的应用，例如数据处理、数据库操作和优化性能等场景。以下是文中提到的三种排序算法的详细解析： 1. **冒泡排序**： 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。在这个例子中，代码实现了将一个整数数组按降序排列的过程。冒泡排序的时间复杂度为O(n²)。 ```c // 冒泡排序 for(int i = 0; i < num - 1; i++) { for(int j = 0; j < num - 1 - i; j++) { if(array[j] < array[j+1]) { int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } ``` 2. **选择排序**： 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。在示例中，代码实现了将一个整数数组按升序排列的过程。选择排序的时间复杂度也为O(n²)，但在某些特定情况下，如部分有序的数组，表现可能优于冒泡排序。 ```c // 选择排序 void sort(int a[], int n) { int i, j, index; for(i = 0; i < n - 1; i++) { index = i; for(j = i + 1; j < n; j++) { if(a[index] > a[j]) { index = j; } } if(index != i) { int temp = a[i]; a[i] = a[index]; a[index] = temp; } } } ``` 3. **快速排序**： 快速排序是由C.A.R. Hoare提出的，它是一种采用分治策略的排序算法。基本步骤包括：选择一个基准元素，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。文中虽然提到了快速排序的起点，但未给出完整的代码实现。快速排序的平均时间复杂度为O(n log n)，最坏情况为O(n²)，但这种情况非常罕见。 ```c // 快速排序起点 void sort(int* a, int left, int right) { if(left >= right) { return; } int i = left; int j = right; int key = a[left]; while(i < j) { while(i < j && key >= a[j]) { j--; } // ... } } ``` 这三种排序算法各有优劣，冒泡排序和选择排序简单易懂，但效率较低；快速排序则在大多数情况下表现出较好的性能，但在最坏情况下效率下降。在面试中，理解这些排序算法的基本原理，以及它们的时间复杂度和适用场景，对于展示编程基础和问题解决能力非常重要。