题解 | #C++冒泡排序#

#include <iostream>
#include<vector>
#include<array>
using namespace std;

void selectSort(vector<int> &v){
  int len = v.size();
  for(int i=0;i<len;i++){
     int min = v[i];
     int id = i;
     for(int j=i+1;j<len;j++){
         if(v[j]<min){
             min = v[j];
             id =j;
         }
     }
     if(id!=i){
         v[id]=v[i];
         v[i]=min;
     }
  }
}

void maopaoSort(vector<int> &v){
  int len = v.size();
  for(int i=0;i<len;i++){
     for(int j=0;j<len-i-1;j++){
         if(v[j]>v[j+1]){
           int temp = v[j+1];
           v[j+1]= v[j];
           v[j] = temp;
         }
     }
  }
}


void charuSort(vector<int> &v){
  int len = v.size();
  for(int i=1;i<len;i++){
     for(int j=i;j> 0;j--){
         if(v[j] < v[j-1]){
           int temp = v[j-1];
           v[j-1]= v[j];
           v[j] = temp;
         }else{
             break;
         }
     }
  }
}

void merge(vector<int> &v,int start,int end){
     int mid = (start + end ) >> 1;
     int arr[end-start+1] = {};
     int i = start;
     int j = mid +1;
     int k = 0;
     while (i <=mid && j<=end) {
         if(v[i]<=v[j]){
             arr[k++]=v[i++];
         }else{
             arr[k++]=v[j++];
         }
     }
     for(int s =i;s<=mid;s++){
         arr[k++]=v[s];
     }
     for(int s =j;s<=end;s++){
         arr[k++]=v[s];
     }
     for(int s =0;s<end-start+1;s++){
         v[start+s]= arr[s];
        // cout << s << "" << arr[s] << endl;
     }
    // cout  << endl;
}

void binGuiSort(vector<int> &v,int start,int end){
  if(start>=end){
      return;
  }
  int mid = (start + end ) >> 1;
  binGuiSort(v,start,mid);
  binGuiSort(v,mid+1,end);
  merge(v,start,end);
}

void quicklySort(vector<int> &v,int start,int end){
    if(start>=end){
        return;
    }
    int base = v[start];
    int baseIndex = start;
    int i = start;
    int j = end;
    while(i<j){
        // 右边
        while (i<j && v[j]>=base) {
            j--;
        }AA
        if(i<j){
            v[baseIndex] = v[j];
            baseIndex = j;
            i++;
        }
        // 左边
        while (i<j && v[i]<=base) {
            i++;
        }

        if(i<j){
            v[baseIndex] = v[i];
            baseIndex = i;
            j--;
        }
        v[i]=base;
    }
    quicklySort(v,start,i-1);
    quicklySort(v,i+1,end);

}

void printArr(vector<int> &v){
  int len = v.size();
  for(int s : v){
      cout << s << " ";
  }
  cout << endl;
}
void test(){
    int n;
    cin >> n;
    vector<int> v =  vector<int>(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    printArr(v);
    //  selectSort(v);
    // maopaoSort(v);
    //charuSort(v);
    //binGuiSort(v,0,n-1);
    quicklySort(v,0,n-1);
    printArr(v);
    cout << "test end " << endl;
}

int main()
{
    while(true){
        test();
    }
    return 0;
}