九大经典算法

1. 冒泡排序（Bubble Sort）

两个数比较大小，通过两两交换，像水中的泡泡一样，较大的数下沉，较小的数冒起来。

算法描述：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3.针对所有的元素重复以上的步骤，除了最后一个；

4.重复步骤1~3，直到排序完成。

动画演示图：

oc代码：

- (NSArray*)bubbleSort:(NSArray*)temArr{

NSMutableArray *arr = [NSMutableArray arrayWithArray: temArr];

NSInteger count = arr.count;

for (int i = 0; i < count; i++) { // 循环次数

for (int j = 0; j < count - 1 - i; j++) { //比较次数

if ([arr[j] intValue] > [arr[j+1] intValue]) {

NSNumber *temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

return arr;

}

swift代码：

func bubbleSort(temArr: [Int] ) -> [Int] {

if temArr.count == 0 {

return []

}

var arr = temArray

let count = arr.count

for i in 0..<count { // 循环次数

for j in 0..<count - 1 - i { // 比较次数

if (arr[j] > arr[j + 1] ) {

let temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

return arr

}

2.快速排序

1.从数列中挑出一个元素作为基准。

2. 重新排列数列，把所有的比基准小的放在基准前面，反之放在后面（一样大可任意一边）完成后基准处在分区的中间位置。

3. 通过递归调用把小于基准元素和大雨基准元素的子序列进行排序

算法过程图：

oc代码：

//数据数组

NSArray *temArr = @[@30,@40, @60, @10, @20, @50];

NSMutableArray *arr = [NSMutableArray arrayWithArray:temArr];

[self quickSort:arr low:0 hight: arr.count - 1];

NSLog(@"%@",arr);

- (void)quickSort:(NSMutableArray*)temArr low: (NSInteger)low hight: (NSInteger)hight{

if (low >= hight) {

return;

}

NSInteger i = low;

NSInteger j = hight;

id key = temArr[i]; // 参考基数

while (i < j) {

while (i < j && [temArr[j] intValue] >= [key intValue]) { // 右边j位大于基数位置不变

j--;

}

if (i == j) { // i、j位置重合结束本次循环，当key是目前最小的数时，会出现i=j的情况，

break;

}

temArr[i] = temArr[j]; //右边j位小于基数位置和i位交换

while (i < j && [temArr[i] intValue] <= [key intValue]) {

i++;

}

if (i == j) { // 当key是目前最大的数时(m[j]的前面)，会出现i=j的情况

break;

}

temArr[j] = temArr[i];

}

temArr[i] = key; // i和j重合时本轮循环结束，将key放入i的位置（则左侧数都比key小，右侧数都比key大）

// key 的左右分别进行快速排序

[self quickSort:temArr low:low hight:i - 1]; // 左递归

[self quickSort:temArr low:i + 1 hight:hight]; // 右递归

}

swift代码：

var array = [30,40,60,10,20,50]

quickSort(arr: &array, low: 0, hight: array.count - 1 )

print(array)

func quickSort(arr: inout [Int], low: Int, hight: Int ) {

if low >= hight { // 递归结束条件

return

}

var i = low;

var j = hight;

let key = arr[i] // 基数

while i < j {

// 从右边开始比较，比key大的数位置不变

while i < j && arr[j] >= key {

j -= 1

}

// 只要出现一个比key小的数，将这个数放入左边i的位置

arr[i] = arr[j]

// 从左边开始比较，比key小的数位置不变

while i < j && arr[i] <= key {

i += 1

}

// 只要出现一个比key大的数，将这个数放入右边j的位置

arr[j] = arr[i]

}

arr[i] = key // i和j重合时本轮循环结束，将key放入i的位置（则左侧数都比key小，右侧数都比key大）

// key 的左右分别进行快速排序

quickSort(arr: &arr, low: low, hight: i - 1) // 左递归

quickSort(arr: &arr, low: i + 1, hight: hight) // 右递归

}

3.插入排序（Insertion Sort）

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后；

6.重复步骤2~5。

动画演示图：

OC代码：

- (NSArray*)insertionSort:(NSArray*)temArr{

NSMutableArray *arr = [NSMutableArray arrayWithArray: temArr];

NSInteger count = arr.count;

for (int i = 0; i < count; i++) { // 循环次数

// 从已排序的部分中查找 arr[i] 合适的位置插入

for (int j = i; j > 0; j--) { // 内循环

if ([arr[j-1] intValue] > [arr[j] intValue]) {

NSNumber *temp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = temp;

} else {

// 因前面是已排序的，故当不满足比较条件即可结束内循环(肯定比前面的值更大)

break;

}

}

}

return arr;

}

swift 代码：

func insertSort(temArr: [Int] ) -> [Int] {

if temArr.count == 0 {

return []

}

var arr = temArray

let count = arr.count

for i in 0..<count { // 交换次数

// 从已排序的部分中查找 arr[i] 合适的位置插入

var j = I

while (j > 0) {

if (arr[j-1] > arr[j] ) {

let temp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = temp;

} else {

// 因前面是已排序的，故只要不满足比较条件即可结束内循环，如肯定比前面的值更大

break;

}

j-=1;

}

}

return arr

}

4.希尔排序（Shell Sort）

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素

算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

2. 按增量序列个数k，对序列进行k 趟排序；

3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

动画演示图：

OC代码:

- (NSArray*)shellSort:(NSArray*)temArr{

NSMutableArray *arr = [NSMutableArray arrayWithArray: temArr];

NSInteger count = arr.count; NSInteger gap = count / 2; //间隔系数

while(gap > 0) { // if的作用

for (NSInteger i = gap; i < count; i++) { // 遍数--分组

NSNumber *temp = arr[i];

NSInteger preIndex = i - gap;

while (preIndex >= 0 && [arr[preIndex] intValue] > [temp intValue]) { // 判断位置交换

arr[preIndex + gap] = arr[preIndex];

preIndex -= gap;

}

arr[preIndex + gap] = temp;

}

gap /= 2;

}

return arr;

}

swift代码：

func shellSort(temArr: [Int] ) -> [Int] {

if temArr.count == 0 {

return []

}

var arr = temArray

let count = arr.count

var gap = count / 2 //间隔系数

while gap > 0 { // if的作用

for i in gap..<count { // 遍数--分组

let temp = arr[i]

var preIndex = i - gap

while preIndex >= 0 && arr[preIndex] > temp { // 判断位置交换

arr[preIndex + gap] = arr[preIndex]

preIndex -= gap

}

arr[preIndex + gap] = temp

}

gap /= 2

}

return arr

}

5. 选择排序（Select Sort）

选择排序是直观的排序，从头依次找出最大(或最小值)，和排序元素换位。未排序元素继续重复排序操作。直到排序完毕。双重循环时间复杂度为 O(n^2)

动画演示图：

算法过程图：

OC代码：

//数据数组

NSArray *arr = @[@3,@44, @38, @5, @47, @15, @36, @26, @27, @2, @46, @4, @19, @50, @48];

// 方法调用

NSArray *sortArray = [self selectSort:arr];

NSLog(@"%@",sortArray);

// 选择排序代码

- (NSArray *)selectSort:(NSArray*)temArr{

NSMutableArray *arr = [NSMutableArray arrayWithArray: temArr];

NSInteger count = arr.count;

for (int i = 0; i < count; i++) { // 交换次数

// 先假设每次循环时，最小数的索引为i

int minIndex = i; // 每一个元素都和剩下的未排序的元素比较

for (int j = i + 1; j < count; j++) {

if ([arr[minIndex] intValue] > [arr[j] intValue]) { //寻找最小数

minIndex = j; //将最小数的索引保存

}

}

//经过一轮循环，就可以找出第一个最小值的索引，然后把最小值放到i的位置

NSNumber *temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

return arr;

}

swift 代码：

// 待排序数组

var temArray = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

// 调用方法

let sortArray = selectSort(temArr: temArray)

// 定义选择排序方法

func selectSort2(temArr: [Int] ) -> [Int] {

if temArr.count == 0 {

return []

}

var arr = temArray

let count = arr.count

for i in 0..<count {

// 交换次数

// 先假设每次循环时，最小数的索引为i

var minIndex = i // 每一个元素都和剩下的未排序的元素比较

for j in i+1..<count {

if arr[minIndex] > arr[j] { //寻找最小数

minIndex = j //将最小数的索引保存

}

}

//经过一轮循环，就可以找出第一个最小值的索引，然后把最小值放到i的位置

let temp = arr[i]

arr[i] = arr[minIndex]

arr[minIndex] = temp

}

return arr

}

6.堆排序

思路分析：

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

动图展示：

OC代码：

- (void)heapSort:(NSMutableArray*)arr{

//1.构建大顶堆

for (NSInteger i = arr.count/2 -1 ; i >= 0; i--) {

//从第一个非叶子结点从下至上，从右至左调整结构

[self adjustHeap:arr i:i length:arr.count];

}

//2.调整堆结构+交换堆顶元素与末尾元素

for (NSInteger j = arr.count - 1; j > 0; j--) {

//将堆顶元素与末尾元素进行交换

NSNumber *temp = arr[0];

arr[0] = arr[j];

arr[j] = temp;

//重新对堆进行调整

[self adjustHeap:arr i:0 length:j];

}

}

/** 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） */

- (void)adjustHeap:(NSMutableArray*)arr i: (NSInteger)i length: (NSInteger)length{

NSNumber *temp = arr[i];

for (NSInteger k = i*2+1; k < length; k = k*2+1) {

//如果右孩子大于做孩子，则指向右孩子

if (k+1 < length && [arr[k] intValue]< [arr[k + 1] intValue]) {

k++;

}

//如果最大的孩子大于当前节点，则将大孩子赋给当前节点，修改当前节点为其大孩子节点，再向下走。

if ([arr[k] intValue] > [temp intValue]) {

arr[i] = arr[k];

i = k;

} else {

break;

}

}

//将temp放到最终位置

arr[i] = temp;

}