【算法】各种排序算法

稳定排序

1.直接插入排序 $O(n^{2})$

void insSort(int *arr,int n)
{
    for(int i=0;i<n;i++)
    {
        int tmp=arr[i];
        int j=i-1;
        while(j>=0&&tmp<arr[j])
        {
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=tmp;
    }
}

2.冒泡排序 $O(n^{2})$

void bubSort(int *arr,int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n-i-1;j++)
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
}

3.二路归并排序

按照分治思想，将序列分为若干子序列，子序列有序，然后再将子序列合并为整体有序序列。

大概的步骤是：

确定分界点mid = (l + r) / 2;
递归排序左半边left，右半边right；
归并，将两个数组合二为一。*(利用到了双指针)

int tmp[N];

void merge_sort(int *arr, int l, int r)
{
    if(l >= r) return;
    
    int mid = l + (r - l) / 2;
    
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    
    while(i <= mid && j <= r)
        if(arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];

    while(i <= mid) tmp[k++] = arr[i++];
    while(j <= r) tmp[k++] = arr[j++];
    
    for(int i = l; i <= r; i++)
        arr[i] = tmp[i - l];
}

4.基数排序

桶子排序，按照基数对整个序列进行多次的排序。

不稳定排序

5.选择排序

void selSort(int *arr,int n)
{
    for(int i=0;i<n;i++)
    {
        int MIN_index = i;
        for(int j=i;j<n;j++)
            if(arr[MIN_index]>arr[j]) MIN_index=j;
        swap(arr[MIN_index],arr[i]);
    }
}

6.快速排序

分治。

大概分为以下步骤：

确定分界点x：arr[l] arr[(l+r)/2] q[r]都是可以的；
调整区间，使得x左边都是小于等于x，右边都是大于x；
递归处理左右两端。

其中第2步是比较重要的，一个简单的实现方法就是额外开两个数组a和b，在扫描q的过程，小于等于x的数放入a，大于x的数放入b，最后将两个数组合并就可以了。

void quick_sort(int *arr, int l, int r)
{
    if(l >= r) return;
    
    int x = arr[(l + r) / 2], i = l - 1, j = r + 1;
    
    while(i < j)
    {
        do i++; while(arr[i] < x);
        do j--; while(arr[j] > x);
        if(i < j) swap(arr[i], arr[j]);
    }
    
    quick_sort(arr, l, j);
    quick_sort(arr, j + 1, r);
}

7.希尔排序

希尔排序就是升级版的插入排序。

void sheSort(int *arr,int n)
{
    int gap=n/2;
    while(gap>=1)
    {
        for(int i=gap; i<n; i++)
        {
            int j=i-gap;
            int tmp=arr[i];
            while(j>=0&&tmp<arr[j])
            {
                arr[j+gap]=arr[j];
                j-=gap;
            }
            arr[j+gap]=tmp;
        }
        gap/=2;
    }
}

8.堆排序

https://www.jianshu.com/p/15a29c0ace73
https://www.cnblogs.com/xingyunshizhe/p/11311754.html

堆是一种非线性结构，近似完全二叉树的结构，可以用一个数组去存储这个树结构。
每个节点的值大于其左右儿子叫作大顶堆，每个节点的值小于其左右儿子叫作小顶堆。

使用堆的原因

如果仅仅是需要得到一个有序的序列，使用排序就可以很快完成，并不需要去组织一个新的数据结构。但是如果我们的需求是对于一个随时会有更新的排序，我要随时知道这个排序的最小值或最大值是什么。

c++的priority_queue

c++的priority_queue的实现机制就是使用了大顶堆或小顶堆。


#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
using namespace std;


/**
默认比较函数为less, 大顶堆
**/
void defaultCmpLess() {
    cout << "=========defaultCmpLess(big heap)========" << endl;
    priority_queue<int> q;
    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout <<endl;

}

/**
使用greater比较函数，小顶堆
**/
void useCmpGreater() {
    cout << "=========useCmpGreater(small heap)========" << endl;
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout <<endl;
}


//==========================

struct Node
{
    int x, y;
    Node(int a = 0, int b = 0):x(a), y(b){};
    friend bool operator<(const Node &a, const Node &b);

};
inline bool operator<(const Node &a, const Node &b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y > b.y;
}

/**
运算符重载
**/
void overloadOperator() {
    cout << "=========overload Operator< =========" << endl;
    cout << "a.x < b.x; a.y > b.y" << endl;
    priority_queue<Node> q;
    for (int i = 0; i < 10; i++) {

        q.push( Node( rand()%20, rand()%20 ) );
    }

    while (!q.empty()) {
        cout << q.top().x << "," << q.top().y << endl;
        q.pop();
    } 
    cout << endl;   
}


//=========================
/**
自构建比较函数
**/
struct cmp2
{
    bool operator()(int a, int b) {
        return a < b;
    }
};

void designCmp() {
    cout << "=========designCmp========" << endl;
    cout << "operator a<b" << endl;
    priority_queue<int, vector<int>, cmp2 > q;

    for (int i = 0; i < 10; i++) {
        q.push(rand()%20);
    }

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout <<endl;
}

int main(int argc, char const *argv[])
{   
    defaultCmpLess();
    useCmpGreater();
    overloadOperator();
    designCmp();
}


/**
=========defaultCmpLess(big heap)========
18 18 13 12 10 9 9 7 4 3
=========useCmpGreater(small heap)========
0 0 2 3 5 7 7 9 12 12
=========overload Operator< =========
a.x < b.x; a.y > b.y
19,1
19,9
19,18
17,6
16,15
12,7
10,13
9,17
3,9
0,13

=========designCmp========
operator a<b
17 16 14 13 12 11 8 7 5 5

**/

go实现堆排序

package main

import "fmt"

// Heap 定义堆排序过程中使用的堆结构
type Heap struct {
    arr  []int   // 用来存储堆的数据
    size int     // 用来标识堆的大小
}

// adjustHeap 用于调整堆，保持堆的固有性质
func adjustHeap(h Heap, parentNode int) {
    leftNode := parentNode*2 + 1
    rightNode := parentNode*2 + 2

    maxNode := parentNode
    if leftNode < h.size && h.arr[maxNode] < h.arr[leftNode] {
        maxNode = leftNode
    }
    if rightNode < h.size && h.arr[maxNode] < h.arr[rightNode] {
        maxNode = rightNode
    }

    if maxNode != parentNode {
        h.arr[maxNode], h.arr[parentNode] = h.arr[parentNode], h.arr[maxNode]
        adjustHeap(h, maxNode)
    }
}

// createHeap 用于构造一个堆
func createHeap(arr []int) (h Heap) {
    h.arr = arr
    h.size = len(arr)

    for i := h.size / 2; i >= 0; i-- {
        adjustHeap(h, i)
    }
    return
}

// heapSort 使用堆对数组进行排序
func heapSort(arr []int) {
    h := createHeap(arr)

    for h.size > 0 {
        // 将最大的数值调整到堆的末尾
        h.arr[0], h.arr[h.size-1] = h.arr[h.size-1], h.arr[0]
        // 减少堆的长度
        h.size--
        // 由于堆顶元素改变了，而且堆的大小改变了，需要重新调整堆，维持堆的性质
        adjustHeap(h, 0)
    }
}

func main() {
    // 测试代码
    arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    heapSort(arr)
    fmt.Println(arr)
}