当前位置： 首页 > article >正文

九大经典算法

article 2024/11/20 23:15:43

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; 

}


http://www.kler.cn/a/6735.html

相关文章：

  • 【Python数据可视化分析实战】数据爬取—京东手机品牌信息数据爬取和数据分析与可视化
  • apipost下载安装教程、脚本详细使用教程
  • unity 打包WebGL打开后Input无法输入中文，在手机端无法调用输入法（使用WebGLInput）
  • Label-studio-ml-backend 和YOLOV8 YOLO11自动化标注，目标检测，实例分割，图像分类，关键点估计，视频跟踪
  • Nuxt3 动态路由URL不更改的前提下参数更新，NuxtLink不刷新不跳转，生命周期无响应解决方案
  • ue中使用webui有效果白色拖动条 有白边
  • 蓝桥杯省赛b组练习
  • tomcat进阶
  • doctor安装mysql jdk nginx tomcat
  • 蓝桥杯第23天（Python）（疯狂刷题第6天）
  • JAVA基于J2ME的手机游戏开发和实现——贪吃蛇
  • windows系统上设置conda和pip国内源
  • tmall.service.settleadjustment.modify( 修改结算调整单 )
  • ARM—汇编指令集
  • 2023链动2+1模式详解
  • 【对YOLOv8(ultralytics)打印测试结果的调整】(1)使得map值打印显示从0.551变为55.08 (2)打印出FPS
  • 一个的错误的演化
  • ImportError: cannot import name imread
  • RocketMQ客户端配置详解
  • CentOS7系统安装MySQL 5.7
  • FOR ALL ENTRIES IN 与 INNER JOIN 内表
  • 2023年最全前端React18面试题考点
  • 第4章 封装组件中级篇
  • Vue项目笔记
  • 如何防止服务器数据轻易泄露
  • React+Typescript+Electron 开发跨平台桌面应用教程