©2020-2024 ioDraw All rights reserved,
Privacy Policy
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;
}