数据结构 排序

void bubbleSort(vector<int>&);

void buidHeap(vector<int>&);
void heapSort(vector<int>&);

void qsort(int, int, vector<int>&);
void quickSort(vector<int>&);

int quickSelect(int,int, int , int[]);

void mSort(int, int, vector<int>&, vector<int>&);
void mergeSort(vector<int>&);

void qsort(int low , int high, vector<int>& vec){
    if (low >= high) return;    
    
    // optimization
    int idx =  low + random() % (high - low + 1);
    swap(vec[low], vec[idx]);

    int pivot = vec[low];
    int l = low;
    int h = high;
    while (low < high){
        while (low < high && vec[high] >= pivot){
            high--;
        }
        vec[low] = vec[high];
        while (low < high && vec[low] <= pivot){
            low++;
        }
        vec[high] = vec[low];
    }
    vec[low] = pivot;
    qsort(l, low - 1, vec);
    qsort(low + 1, h, vec);
}
void quickSort(vector<int>& vec){
     qsort(0, static_cast<int>(vec.size())  - 1, vec);
}

int quickSelect(int k ,int low, int high, int vec[]){
    int pivot = low + rand() % (high - low + 1);
    swap(vec[low], vec[pivot]);
    int val = vec[low];
    int l = low, h = high;
    while (low < high){
        while (low < high && vec[high] >= val){
            high--;
        }
        vec[low] = vec[high];
        while (low < high && vec[low] <= val){
            low++;
        }
        vec[high] = vec[low];
    }
    vec[low] = val;
    if (low == k){
        return vec[low];
    } else if (low > k ){
        return quickSelect(k, l, low - 1, vec);
    } else{
        return quickSelect(k, low + 1, h, vec);
    }
}

void bubbleSort(vector<int>& vec){
    for (int i = 0; i  < static_cast<int>(vec.size())  - 1; ++i){
        bool isSorted = true;
        for (int j =  static_cast<int>(vec.size())  - 1; j > i; --j){
            if (vec[j - 1] > vec[j]){
                swap(vec[j - 1], vec[j]);
                isSorted = false;
            }
        }
        if (isSorted == true) 
            break;
    }
}

void buildHeap(vector<int>& heap){
    int len = static_cast<int>(heap.size());
    for (int i = len / 2; i > 0; --i){
        int j = i;
        while (j * 2 <= len) {
            int child =  j * 2;
            if (child + 1 <= len && heap[child] > heap[child - 1]){
                child++;
            }
            if (heap[j - 1] < heap[child - 1]){
                swap(heap[j - 1], heap[child - 1]);
                j = child; 
            } else{
                break;
            }
        }
    }
}

void heapSort(vector<int>& heap){
    buildHeap(heap);
    int len = static_cast<int>(heap.size());
    for (int i = len; i >= 1; --i){
        int j = 1;
        swap(heap[j - 1], heap[i - 1]);
        while (j * 2 <= i - 1) {
            int child =  j * 2;
            if (child + 1 <= i - 1 && heap[child] > heap[child - 1]){
                child++;
            }
            if (heap[j - 1] < heap[child - 1]){
                swap(heap[j - 1], heap[child - 1]);
                j = child; 
            } else{
                break;
            }
        }
    }
}

void mSort(int low, int high, vector<int>& vec, vector<int>& backup){
    if (low >= high)
        return;
    int mid = low + (high - low) / 2;
    mSort(low, mid, vec, backup);
    mSort(mid + 1, high, vec, backup);
    for (int i = low, j = mid + 1, k = low; i <= mid || j <= high; ++k){
        if (j > high || ( i <= mid && vec[i] <= vec[j]) ){
            backup[k] = vec[i++];
        } else{
            backup[k] = vec[j++];
        }
    }
    for (int i = low; i <= high; ++i){
        vec[i] = backup[i];
    }
}
void mergeSort(vector<int>& vec){
    vector<int> backup(vec.size(), 0);
    mSort(0, static_cast<int>(vec.size()) - 1, vec, backup);
}