排序算法

排序算法 时间复杂度 最好情况 最坏情况 空间复杂度
冒泡排序 O(n^2) O(n) O(n^2) O(1)
选择排序 O(n^2) O(n^2) O(n^2) O(1)
插入排序 O(n^2) O(n) O(n^2) O(1)
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n)
快速排序 O(nlogn) O(nlogn) O(nlogn) O(logn)
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1)

注:

​ 表中时间复杂度为平均时间复杂度

​ 稳定性:相同数字是否保持原顺序

​ 排序为升序(除了堆外)

冒泡排序

思路:遍历数组n次(n为数的个数),比较两个数的大小,较大的数下沉,较少的数上浮。

void bubble_Sort(vector<int>& arr){
    int size = arr.size();
    // 第i轮
    for(int i = 0 ; i < size - 1 ; i++){ 
    // 从最后一个数字开始依次向前比较,由于每次将最小的数浮到最上面。
    // 因此,每轮过后 需要比较的次数将减少一次
        for(int j = size - 1 ; j > i ; j--){ 
            if(arr[j] < arr[j-1]){
                swap(arr[j] , arr[j-1]);
            }
        }
	}
}

优化思路:数据数据顺序排好之后,冒泡排序依然会进行下一轮比较,而后面的遍历都是多余的。

因此,可以设置标志位,当某一轮没有发生交换的时候,则结束排序。

eg: 针对 1234576 ,当进行完第一轮比较后,数组已经排序完成,在第二轮比较中,不会发生任何的交换。可以在第二轮之后便结束排序。

void bubble_SortOP(vector<int>& arr){
    int size = arr.size();
    bool flag = false;
    for(int i = 0 ; i < size -1 ; i++){
        flag = false;//每次遍历前设置为false
        for(int j = size -1 ; j > i ; j--){
            if(arr[j] < arr[j-1]){
                swap(arr[j] , arr[j-1]);
                flag = true;// 如果发生一次交换,则设置为true
            }
            if(!flag)// 如果当前轮比较未发生交换,则数据已经排序完成,推出循环。
                break;
        }
    }
}

选择排序

思路:每次选择数组中剩余数最小的,将其放到最前面(与对应位置进行交换)。

void selection_sort(vector<int>& arr) {
    int size = arr.size();
    for (int i = 0; i < size - 1; i++) {
        int minIdx = i;
        for (int j = size - 1; j > i; j--) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
    }
}

插入排序

思路:遍历数组,第K个数分别与前K-1个数进行比较,并且找到自己的位置。

void insertion_Sort(vecotr<int>& arr){
    int size = arr.size();
    for(int i = 1 ; i < size ; i++){
        for(int j = i ; j > 0 ; j--){
            if(arr[j] < arr[j-1]){
                swap(arr[j] , arr[j-1]);
            }else{
                break;
            }
        }
    }
}

归并排序

思想:采用分治法 ,将数组分成两组 A和B,如果A 、B组内有序,那么归并这两个子序列就能够得到有序序列。如下图所示:**

void merge_Sort(vector<int>& arr , int begin , int end){
    if(begin < end){
        int mid = (begin + end)/2;
        merge_Sort(arr , begin , mid);// 排序左半部分
        merge_Sort(arr , mid + 1 , end);// 排序右半部分
        merge(arr , begin , mid , end);// 合并左右部分
    }
}

void merge(vector<int>& arr , int begin , int mid , int end){
    int i = 0 , j = 0 , k = 0 , size = end - begin + 1 ; 
    vector<int> temp(size , 0);
    int pLeft = begin , pRight = mid + 1 ;
    bool endLeft = false , endRight = false;
    for( i = 0 , i < size ; i++){
        if(!endLeft && !endRight) {
            if(arr[pLeft] < arr[pRight]){
                temp[i] = arr[pLeft++];
            }else {
                temp[i] = arr[pRight++];
            }
            // 判断是否到达终点
            if(pLeft > mid)
                endLeft = true;
            if(pRight > end)
				endRight = true;            
        } else {
            // 至少一个达到终点
            if(!endLeft)
                temp[i] = arr[pLeft++];
            else
                temp[i] = arr[pRight++];
        }
        for(j = 0 ; k = begin ; j < size ; j++ , k++){
            arr[k] = temp[j];
        }
    }
 
}

快速排序

思想:分治法,先从序列中选出一个数作为pivot,将比这个数小的数放在其左边,大的数放在其右边。然后,对左右两个子序列重复以上步骤,直到各子区间只有一个数。具体如下图所示:

int find_Pivot(vector<int>& arr, int begin, int end) { // 返回arr[begin], arr[mid], arr[end]的中间值
    int mid = (begin + end)/2;
    if (arr[begin] < arr[end]) {
        if (arr[end] < arr[mid]) {
            return end;
        } else if (arr[begin] > arr[mid]) {
            return begin;
        } else {
            return mid;
        }
    } else {
        if (arr[end] > arr[mid]) {
            return end;
        } else if (arr[begin] < arr[mid]) {
            return begin;
        } else {
            return mid;
        }
    }
}

int partition(vector<int>& arr, int begin, int end, int pivot) {
    while (true) {
        while (arr[begin] < pivot) { // 从左开始找到第一个比pivot大的值
            begin++;
        }
        end--; // 调整(若不调整,会将放在end处的pivot交换到别的位置)
        while (arr[end] > pivot) { // 从右开始找到第一个比pivot小的值
            end--;
        }
        if (begin >= end) {
            return begin; // 返回比pivot大的第一个值,即右序列的第一个位置
        } else {
            swap(arr[begin], arr[end]);
            begin++; // 调整
        }
    }
}

void quick_sort(vector<int>& arr, int begin, int end) {
    if (begin >= end) {
        return;
    } else {
        int pivotIdx = find_Pivot(arr, begin, end);
        swap(arr[pivotIdx], arr[end]); // 将pivot放在序列末尾
        int bgRight = partition(arr, begin, end, arr[end]); // partition的返回值为右序列(比pivot大)的第一个位置,注意pivot已经被交换到末尾,故传入的pivot为arr[end]
        swap(arr[bgRight], arr[end]); // 将pivot值放回中间,使左序列比pivot大,右序列比pivot小
        quick_sort(arr, begin, bgRight-1); // 对左序列重新排序
        quick_sort(arr, bgRight+1, end); // 对右序列重新排序
    }
}

堆排序

思想:

class HEAP {
private:
    int heapSize;
    vector<int> harr;

public:
    HEAP() {
        heapSize = 0;
    }
    
    HEAP(vector<int>::iterator begin, vector<int>::iterator end) {
        heapSize = 0;
        for (auto it = begin; it != end; it++) {
            insert(*it);      
        }
    }
    
    int parent(int i) {
        return (i - 1) / 2;
    }
    
    int left(int i) {
        return 2 * i + 1;
    }
    
    int right(int i) {
        return 2 * i + 2;
    }
    
    void display() {
        for (int i = 0; i < heapSize; i++) {
            cout << harr[i] << " ";
        }
    }
    
    void insert(int num) {
        harr.push_back(num); // 将新数插入至末尾
        heapSize++;
        int idx = heapSize - 1; // 取新数的索引
        while (idx >= 0 && harr[parent(idx)] > harr[idx]) { // 将新数交换至正确的位置
            swap(harr[parent(idx)], harr[idx]);
            idx = parent(idx);
        }
        for (int i = 0; i < heapSize; i++) {
            cout << harr[i] << " ";
        }
        cout << endl;
    }
    
    void minheapify(int idx, int boundry) {
        int leftIdx = left(idx); // 取idx左边子节点
        int rightIdx = right(idx); // 取idx右边子节点
        if (leftIdx >= boundry || rightIdx >= boundry) { // 判断剩余元素是否已经成堆
            return ;
        }
        int minIdx = idx; // 记录最小元素的索引
        if (harr[leftIdx] < harr[idx]) {
            minIdx = leftIdx;
        }
        if (harr[rightIdx] < harr[minIdx]) {
            minIdx = rightIdx;
        }
        if (minIdx != idx) {
            swap(harr[idx], harr[minIdx]);
            minheapify(minIdx, boundry);
        }
    }
    
    vector<int> sort() {
        for (int i = 1; i < heapSize - 1; i++) {
            swap(harr[0], harr[heapSize - i]); // 每次将最小元素移到后面去(移出堆中)
            minheapify(0, heapSize - i); // 将剩下的元素重新调节成最小堆
        }
        if (harr[0] < harr[1]) {
            swap(harr[0], harr[1]);
        }
        return harr;
    }
};