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

03 冒泡排序(Bubble Sort)

每次选择两个元素，按照需求进行交换（比如需要升序排列的话，把较大的元素放在靠后一些的位置），循环 n 次（n 为总元素个数），这样小的元素会不断 “冒泡” 到前面来。

普通版

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

进阶版

void bubbleSort(int arr[],int n)
{
      bool swapp = true;
      while(swapp){
        swapp = false;
        for (int  i = 0; i < n - 1; i++) { //这里的n要减1
            if (arr[i] > arr[i+1] ){
                arr[i] += a[i+1];
                arr[i+1] = arr[i] - arr[i+1];
                arr[i] -=a[i+1];
                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[low];
        while (low < high) {            
            while (low < high && arr[high] >= tmp) {
                high--;
            }            
            arr[low] = arr[high];            
            while (low < high && arr[low] <= tmp) {
                low++;
            }            
            arr[high] = arr[low];
        }        
        arr[low] = tmp;
        return low; 
 }
void quick_sort(int arr[], int low, int high){
    if(low < high){
        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(low < high){
        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[low];
    while(low < high){
        while(low < high && arr[high] >= tmp){
            high--;
        }
        arr[low] = arr[high];
        while(low < high && arr[low] <= tmp){
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = tmp;
    return low;
}

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

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

具体代码实现

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

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

时间效率：最好情况：O(Nlog₂N)                  平均情况：O(Nlog₂N)                       最坏情况：O(N²)

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