论坛 › 教程 › 九大经典算法之冒泡排序、快速排序

seo 发表于 2022-5-31 13:35:51

九大经典算法之冒泡排序、快速排序

九大经典算法之冒泡排序、快速排序发布时间：2022/5/31 12:53:39
            
                                                       
                                                       
            
      
      
               
                     
03 冒泡排序(Bubble Sort)
每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来。

普通版


void bubbleSort(int arr[],int n){//标准版
      for(int i = 0; i 1; i++){
          for(int j = 0; j 1 - i; j++){
            if(arr > arr){
                  arr += arr;
                  arr = arr - arr;
                  arr -= arr;
            }
          }
      }   
}

进阶版


void bubbleSort(int arr[],int n)
{
      bool swapp = true;
      while(swapp){
      swapp = false;
      for (inti = 0; i ) { //这里的n要减1
            if (arr > arr ){
                arr += a;
                arr = arr - arr;
                arr -=a;
                swapp = true;
            }
      }
    }
}

空间效率：O(1)

时间效率：最好情况：O(n)             平均情况：O(N^2)                     最坏情况：O(N^2)

稳定性（相同元素相对位置变化情况）：稳定

04 快速排序（Quick Sort）
快排是一个分治的算法，快排算法每次选择一个元素并且将整个数组以那个元素分为两部分，整个快速排序的核心是分区（partition），分区的目的是传入一个数组和选定的一个元素，把所有小于那个元素的其他元素放在左边，大于的放在右边。

根据实现算法的不同，元素的选择一般有如下几种：

       1. 永远选择第一个元素

       2. 永远选择最后一个元素

       3. 随机选择元素

       4. 取中间值



int partition(int arr[], int low, int high){
      int tmp = arr;
      while (lowhigh) {            
            while (low = tmp) {
                high--;
            }            
            arr = arr;            
            while (lowtmp) {
                low++;
            }            
            arr = arr;
      }      
      arr = tmp;
      return low;
}
void quick_sort(int arr[], int low, int high){
    if(lowhigh){
      int pivotpos = partition(arr,low,high);
      quick_sort(arr,low,pivotpos-1);
      quick_sort(arr,pivotpos+1,high);
    }
}


修改统一接口


void quickSort(int arr[],int n){
    quick_sort(arr,0,n-1);
}
void quick_sort(int arr[],int low,int high){
    if(lowhigh){
      int pivotpos = partition(arr,low,high);
      quick_sort(arr,low,pivotpos-1);
      quick_sort(arr,pivotpos+1,high);
    }
}
int partition(int arr[],int low,int high){
    int tmp = arr;
    while(lowhigh){
      while(low = tmp){
            high--;
      }
      arr = arr;
      while(lowtmp){
            low++;
      }
      arr = arr;
    }
    arr = tmp;
    return low;
}



算法导论中提供了另一种partition 的思路



int partition(int arr[], int low, int high){
    int pivot = arr;
    int i = low - 1;
    for(int j = low; j 1; j++){
      if(arrpivot){
            i++;
            arr += arr;
            arr = arr - arr;
            arr = arr - arr;
      }
    }
    inttemp = arr;
    arr = arr;
    arr = temp;
    return (i+1);
}

具体代码实现


   int partition(int arr[],int low,int high){
      int pivot = arr;
      int i = low - 1;
      for(int j = low; j 1; j++){
          if(arrpivot){
            i++;
            int temp = arr;
            arr = arr;
            arr = temp;
            //arr += arr;这种交换数值结果出错
             //arr = arr - arr;
             //arr -= arr;
          }
      }
      int temp = arr;
      arr = arr;
      arr = temp;
      //arr += arr;
      //arr = arr - arr;
      //arr -= arr;
      return i+1;
}

空间效率：最好情况:   O(log2(N+1))    平均情况 : O(log2N)                     最坏情况 ： O(log2N)

时间效率：最好情况：O(Nlog2N)                  平均情况：O(Nlog2N)                     最坏情况：O(N2)

稳定性（相同元素相对位置变化情况）：稳定


转载于:https://www.cnblogs.com/wanghao-boke/p/10421133.html
               
      
      
   
            
      
      
https://www.yilongzhijia.cn/tupian/seo365t.jpg

查看完整版本: 九大经典算法之冒泡排序、快速排序