1. 排序算法

1.1. 排序算法比較

排序算法	平均時間復(fù)雜度	最差時間復(fù)雜度	空間復(fù)雜度	數(shù)據(jù)對象穩(wěn)定性
冒泡排序	O(n²)	O(n²)	O(1)	穩(wěn)定
選擇排序	O(n²)	O(n²)	O(1)	數(shù)組不穩(wěn)定宿饱，鏈表穩(wěn)定
插入排序	O(n²)	O(n²)	O(1)	穩(wěn)定
快速排序	O(nlog₂n)	O(n²)	O(log₂n)	不穩(wěn)定
歸并排序	O(nlog₂n)	O(nlog₂n)	O(n)	穩(wěn)定
希爾排序	O(nlog₂n)	O(n²)	O(1)	不穩(wěn)定
堆排序	O(nlog₂n)	O(nlog₂n)	O(1)
計(jì)數(shù)排序	O(n+k)	O(m+n)	O(k)	穩(wěn)定
桶排序	O(n+k)	O(n)	O(n+k)	穩(wěn)定
基數(shù)排序	O(n*k)	O(n²)	O(n+k)	穩(wěn)定
錦標(biāo)賽排序

1.2. 排序算法詳解

1.2.1. 起泡排序

insertionSort

起泡排序思路：
1. 比較相鄰的元素熏瞄。如果第一個比第二個大，就交換他們兩個谬以。
2. 對每一對相鄰元素作同樣的工作强饮，從開始第一對到結(jié)尾的最后一對。這步做完后蛉签，最后的元素會是最大的數(shù)胡陪。
3. 針對所有的元素重復(fù)以上的步驟沥寥，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟柠座，直到?jīng)]有任何一對數(shù)字需要比較邑雅。

void swap(int & a, int & b) {
    int c = a;
    a = b;
    b = c;
}
int bubble(int *num, int m) {
    int flag = 0;
    for (int i = 1; i < m; i++) {
        if (num[i-1] > num[i]) {
            swap(num[i-1], num[i]);
            flag = i;
        }
    }
    return flag;
}
void bubbleSort(int *num, int n) {
    int fl = bubble(num, n);
    while (fl) {
        fl = bubble(num, fl);
    }
}

1.2.2. 選擇排序

image

選擇排序思路：
1. 在未排序序列中找到最小（大）元素妈经，存放到排序序列的起始位置
2. 從剩余未排序元素中繼續(xù)尋找最谢匆啊（大）元素，然后放到已排序序列的末尾
3. 以此類推吹泡，直到所有元素均排序完畢

void SelectionSort(vector<int>& v) {
    int min, len = v.size();
    for (int i = 0; i < len - 1; ++i) {
        min = i;
        for (int j = i + 1; j < len; ++j) {
            if (v[j] < v[min]) {    // 標(biāo)記最小的
                min = j;
            }
        }
        if (i != min)  // 交換到前面
            swap(v[i], v[min]);
    }
}

// 模板實(shí)現(xiàn)
template<typename T> 
void Selection_Sort(std::vector<T>& arr) {
    int len = arr.size();
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++)
            if (arr[j] < arr[min])
                min = j;
        if(i != min)
            std::swap(arr[i], arr[min]);
    }
}

1.2.3. 插入排序

image

插入排序思路：
1. 從第一個元素開始骤星，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素爆哑，將該元素移到下一位置
4. 重復(fù)步驟3洞难，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置后
6. 重復(fù)步驟2~5

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

1.2.4. 快速排序

image

快速排序思路：
1. 選取第一個數(shù)為基準(zhǔn)
2. 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
3. 對左右區(qū)間重復(fù)第二步揭朝，直到各區(qū)間只有一個數(shù)

int partition(vector<int> & num, int lo, int hi) {
    int pivot = num[lo];
    int temp = lo;
    while (lo < hi) {
        while ((lo < hi) && (pivot <= num[hi]))
            hi--;
        num[lo] = num[hi];
        while ((lo < hi) && (pivot >= num[lo]))
            lo++;
        num[hi] = num[lo];
        //std::swap(num[hi], num[lo]);
    }
    num[lo] = pivot;
    //std::swap(num[lo], num[temp]);
    //for (auto w : num)
    //  cout << w << "  ";
    //cout << endl;
    return lo;
}

void quickSo(vector<int> & num, int lo, int hi) {
    if (hi - lo < 2)
        return;
    int mi = partition(num, lo, hi - 1);
    quickSo(num,lo, mi);
    quickSo(num,mi + 1, hi);
}

void quickSort(vector<int> & num) {
    quickSo(num, 0, num.size());
}

迭代實(shí)現(xiàn)

// ----------------------------------------------------

// 模板實(shí)現(xiàn)快速排序（迭代）
struct Range {
    int start, end;
    Range(int s = 0, int e = 0) {
        start = s, end = e;
    }
};
template <typename T> // 整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時必須設(shè)定"小於"(<)队贱、"大於"(>)、"不小於"(>=)的運(yùn)算子功能
void quick_sort(T arr[], const int len) {
    if (len <= 0)
        return; // 避免len等於負(fù)值時宣告堆疊陣列當(dāng)機(jī)
    // r[]模擬堆疊,p為數(shù)量,r[p++]為push,r[--p]為pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        T mid = arr[range.end];
        int left = range.start, right = range.end - 1;
        while (left < right) {
            while (arr[left] < mid && left < right) left++;
            while (arr[right] >= mid && left < right) right--;
            std::swap(arr[left], arr[right]);
        }
        if (arr[left] >= arr[range.end])
            std::swap(arr[left], arr[range.end]);
        else
            left++;
        r[p++] = Range(range.start, left - 1);
        r[p++] = Range(left + 1, range.end);
    }
}

1.2.5. 歸并排序

image

核心思想：分而治之
實(shí)現(xiàn)步驟：

void MergeSort(){
    遞歸條件
    分組1
    分組2
    歸并
}

遞歸實(shí)現(xiàn)

template<typename T>
void merge(vector<T> &num, int lo, int mi, int hi) {
    int lb = mi - lo;
    int lc = hi - mi;
    T *pa = &num[lo];
    T *pb = new T[lb];
    T *pc = &num[mi];
    for (int i = 0; i < lb; i++) {
        pb[i] = pa[i];
    }
    for (int m = 0, n = 0, k = 0; (m < lb) || (n < lc);) {
        if ((m < lb) && ((n >= lc) || (pb[m] < pc[n])))
            pa[k++] = pb[m++];
        else
            pa[k++] = pc[n++];
    }
}
template <typename T>
void mergeSort(vector<T> & A,int lo, int hi) {
    if (hi - lo < 2)        //遞歸條件
        return;
    int mi = (hi + lo) >> 1;
    mergeSort(A,lo, mi);
    mergeSort(A,mi, hi);
    merge(A,lo, mi, hi);
}

迭代實(shí)現(xiàn)

template<typename T>
void merge_sort(T arr[], int len) {
    T* a = arr;
    T* b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

1.2.6. 希爾排序

算法思想：
算法思想來源于插入排序潭袱，
先將n個待排序的序列分割成n/2組數(shù)據(jù)分別進(jìn)行插入排序柱嫌，
然后依次分割成n/4組,n/8組,
直至最后只能分成一組數(shù)據(jù)進(jìn)行插入排序
算法演示：

1940317-0f04f8b6aec097bb

算法實(shí)現(xiàn)：

//希爾排序
void shellSort(int *p, int n) {
    int temp = n;
    while (temp >>= 1) {
        for (int i = temp; i < n; i++) {
            for (int j = i; j > 0; j -= temp) {
                if (p[j] < p[j - temp]) {
                    Swap(p[j], p[j - temp]);
                    break;
                }
            }
        }
    }
}

1.2.7. 計(jì)數(shù)排序

算法思想：
對值比較集中的數(shù)據(jù)進(jìn)行排序先統(tǒng)計(jì)每個數(shù)據(jù)個數(shù)，再根據(jù)個數(shù)進(jìn)行排序

算法圖解

countingSort

算法實(shí)現(xiàn)

//計(jì)數(shù)排序
void countSort(int *p, int n) {
    int max = p[0];
    int min = p[0];
    for (int i = 0; i < n; i++) {       //找到最小與最大值
        if (max < p[i])
            max = p[i];
        if (min > p[i])
            min = p[i];
    }
    int space = max - min + 1;          
    int *num = new int[space]();        //申請輔助空間
    for (int i = 0; i < n; i++) {       //統(tǒng)計(jì)
        num[p[i] - min]++;
    }
    int j = 0;
    for (int i = 0; i < space; i++) {   //排序
        while (num[i]--) {
            p[j++] = i+min;
        }
    }
    delete[]num;
}

1.2.8. 桶排序

1.2.9. 基數(shù)排序

image

1.2.10. 堆排序

image

排序算法總結(jié)

排序算法總結(jié)

1. 排序算法

1.1. 排序算法比較

1.2. 排序算法詳解

1.2.1. 起泡排序

1.2.2. 選擇排序

1.2.3. 插入排序

1.2.4. 快速排序

1.2.5. 歸并排序

1.2.6. 希爾排序

1.2.7. 計(jì)數(shù)排序

1.2.8. 桶排序

1.2.9. 基數(shù)排序

1.2.10. 堆排序