各种排序算法总结

1.插入排序

//插入排序
void inssort(int a[],int n) {
    //一个元素天然就是排好序的，所以i从1开始循环
    for (int i = 1; i < n; i++) {
        //后面的比前面相邻的元素小，交换这两个元素
        for (int j = i; j > 0 && (a[j] < a[j - 1]); j--)
            swap(a[j], a[j - 1]);
    }
}

2.冒泡排序

//冒泡排序
//第i次循环，保证前面i个元素是有序的

void bubsort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        //j每次都从末尾开始循环，如果前面相邻的元素比后面大，就交换这两个元素，直至j=i为止
        for (int j = n - 1; j>i; j--) {
            if (a[j] < a[j - 1])
                swap(a[j], a[j - 1]);
        }
    }
}

3.选择排序

//选择排序
//第i次循环找第i小的元素
void selection(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        swap(a[i], a[min]);
    }
}

4.快速排序

int partition(int a[], int l, int r, int &pivot) {
    while (l < r) {
        while (a[l] < pivot)//找到a[l]>=pivot
            l++;
        while (r > l&&a[r] >= pivot)//找到a[r]<piovt
            r--;
        swap(a[l], a[r]);//交换a[l],a[r]
    }//l和r相遇的位置就是划分点最后该待在的位置
    return l;
}

//快速排序
void qsort(int a[], int i, int j) {
    if (i>=j)
        return;
    //取哪个位置作为划分点
    int pivotindex = (i + j) / 2;
    //将划分点元素移到数目末尾
    swap(a[pivotindex], a[j]);
    //调用partition函数，保证k左边的元素比a[j]小，右边的元素比a[j]大(或者等于)
    int k = partition(a, i, j, a[j]);
    //将pivot移动到合适的位置
    swap(a[k], a[j]);
    //递归对pivot左右半边数组调用qsort函数
    qsort(a,i,k-1);
    qsort(a, k + 1, j);
}

5.归并排序

//归并排序
void mergesort(int a[],int l,int r) {
    if (l >=r)
        return;
    int mid = (l + r) / 2;
    //递归对左右半边进行排序
    mergesort(a, l, mid);
    mergesort(a, mid + 1, r);
    //用于排序的辅助数组，其左半边和a[l->mid]一致，右半边则是a[r->mid],保证了中间大，两边小
    int *temp = new int[r + 1];
    //复制左半边的数组
    for (int i = l; i <= mid; i++) 
        temp[i] = a[i];
    //复制右半部分的数组，注意顺序要反过来
    int j = mid + 1;
    for (int i = r ; i > mid; i--) {
        temp[j++] = a[i];
    }
    //从辅助数组两边，选择较小的那个数作为排序后的第k个元素
    for (int i = l, j = r, k = l; k <= r; k++) {
        if (temp[i] < temp[j])
            a[k] = temp[i++];
        else
            a[k] = temp[j--];
    }
}

6.堆排序

class max_heap {
public:
    int *a;
    int n;
    int size;
    max_heap(int a[], int n) {//构造函数
        this->a = a;
        this->n = n;
        size = n;
        //建堆
        for (int i = n / 2-1; i > -1; i--)
            siftdown(i);
    }
    void heapsort() {
        while(n>0){//当剩余元素大于0个
            swap(a[0], a[--n]);//当前最大的元素和数组末尾元素交换
            siftdown(0);//对调换之后的根节点元素进行siftdown处理
        }
    }
    
    void siftdown(int pos) {//l=2*pos+1,r=2*pos+2
        while ((2 * pos + 1) < n) {
            int l = 2 * pos + 1;
            int r = l + 1;
            if (r<n&&a[r]>a[l])//l代表叶子节点中较大的那一个的下标
                l = r;
            if (a[l] > a[pos]) {//如果根节点比叶子节点中较大的那个小
                swap(a[l], a[pos]);//交换
                pos = l;//继续处理下一层节点
            }
            else
                break;
        }
    }
        void print() {//输出数组中的所有元素
            for (int i = 0; i < size; i++)
                cout << a[i] << " ";
            cout << endl;
        }    

};