重拾数据结构之排序

1、Bubble Sort Implementation （冒泡排序）
Solution：

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]){
                __swap(arr[j], arr[j + 1]);
            }
        }
    }

}

2、Selection Sort Implementation （选择排序）
Solution：

void selectionSort(int arr[], int n){

    for ( int i = 0; i < n; i++){

        int min = i;

        for ( int j = i + 1; j < n; j++){

            if (arr[min] > arr[j]){
                min = j;
            }
        }

        if (min != i){
            __swap(arr[i], arr[min]);
        }

    }

}

3、Insertion Sort Implementation（插入排序）
Solution：

void insertionSort(int arr[], int n){

    for ( int i = 1; i < n; i ++){

        for (int j = i; j > 0; j --){

            if (arr[j] < arr[j - 1]){

                __swap(arr[j], arr[j-1]);

            }else{

                break;

            }
        }
    }
}

4、Quick Sort Implementation （快速排序）

int __partition2Way(int arr[], int l , int r){
    
    //pivot is the random element in array
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    int pivot = arr[l];
    
    int i = l + 1, j = r;
    
    //l+1,i    j,r
    while (true) {
        
        while (i <= r && arr[i] < pivot) {
            i++;
        }
        
        while (j >= l + 1 && arr[j] > pivot) {
            j--;
        }
        
        if (i > j) {
            break;
        }
       
        swap(arr[i], arr[j]);
        
        i++;
        j--;
    }
    
    swap(arr[l], arr[j]);
      
    return j;
}

排序：https://blog.csdn.net/u010926964/article/details/40045501