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; 

}

技术
今日推荐
阅读数 170189
阅读数 23
阅读数 5
阅读数 0
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信