亲宝软件园·资讯

展开

【紫书】算法竞赛之排序算法笔记

Vincent& 人气:1

一:冒泡排序(O(n^2))

每组每个位置的数与它后面的数比较,前面数大于后面的数就交换数值,交换n-1组。

每次每组交换的时候,都会把最大的排到后面去,就类似与在水底泡泡慢慢的向上浮出。

特性:

稳定。

动图演示:

详细解析代码:

#include<stdio.h>

int main() {
    int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
    //为了方便大家理解,我将数值设为与动图一样的数值。

    int n = 15;
    //冒泡排序
    for(int i=0;i<n-1;i++)//代表的是要做多少组比对,为什么是n-1呢?
        //因为计数从0开始而且第一个数和自身没有比对的必要性。
        for(int j=0;j<n-1-i;j++)
        //代表组里面的序号,因为要与后面数做比较,而最后一个数没有与之比较的(可能会越界)所以n-1
        //为什么还要-i呢?
        //因为每排过一遍,这一组最大值就排到后面去了,也就没必要再去比较了。
            if (a[j] > a[j + 1]) {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }

    for (int i = 0;i < n;i++)
        printf("%d ", a[i]);

    return 0;
}

 

二、选择排序(O(n^2))

设置两重循环,第一重循环做为比较的基准,第二重循环找它后面比它小的数,然后与之交换。

就是选择一个它后面的所有比他小的数中的最小的数进行交换,冒泡排序是固定后面的数,而选择排序是固定前面的数。

特性:

移动数据的次数已知(n-1 次)。

动图演示:

 

  

详细解析代码:

#include<stdio.h>

int main() {
    int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
    //为了方便大家理解,我将数值设为与动图一样的数值。

    int n = 15;
    //选择排序
    for (int i = 0;i < n - 1;i++) // 代表的是要做基数数值的下标,为什么是n - 1呢?
        //因为计数从0开始而且最后一个数没得数和它进行比较了。
    {
        int k = i;
        for (int j = i + 1;j < n;j++)//找到比基数小的数中的最小数的下标
            if (a[k] > a[j]) k = j;

        if (k != i) {
            int temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }

    for (int i = 0;i < n;i++)
        printf("%d ", a[i]);

    return 0;
}

 

三、插入排序(O(n^2))

从第二个数开始,将数字抽出来与前面的数依次比较,大于它的统统向后移动一格。

也就是将抽出来的数放到它该在的位置。

特性:

在大多数元素已经有序的情况下,插入排序的工作量较小。

动图演示:

详细解析代码:

#include<stdio.h>

int main() {
    int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
    //为了方便大家理解,我将数值设为与动图一样的数值。

    int n = 15;
    //选择排序
    for (int i = 1;i < n ;i++) // 代表的是要放回原位数数值的下标
    {
        int front = i- 1;//初始化前一个数的下标
        int sum = a[i];//放回原位数数值
        while (front >= 0 && a[front] > sum)
            //防止数组越界并且前面数比后面的数大才能继续
            a[front + 1] = a[front--];
        //把前面数向后移动,前一个数的下标-1,,想象动图中空格的变化

        //上个循环结束了,说明空格不能再变化了,将其赋值回去就好了
        a[++front] = sum;
    }

    for (int i = 0;i < n;i++)
        printf("%d ", a[i]);

    return 0;
}

四、归并排序 O(nlog(2)n)

特性:

可顺便处理逆序对的问题。

动图演示:

这个算法用动图充分体现了它的思想,放在下面的是辅助数组,将每部分以两段两段的分开进行排序,分开的排好了,再进行总的排序。

详细解析代码

#include<stdio.h>

int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解,我将数值设为与动图一样的数值。
int t[20];//辅助数组,中转站的意思。

void merge_sort(int l, int r) {
 //如果两个数组下标相邻,就不必要再进行二分了,再分就只有一个了,无法比较了。
    if (r - l > 1) {
        int m = l + (r - l >> 1), i = l, j = m, k = l;
        //m为分开的的这一段的中间下标,i为左边起始点,j为右边起始点,k为辅助数组起始点。
        //将总的一段二分。
        merge_sort(l, m);
        merge_sort(m, r);

        //然后再将这两段归并到一起进行排序。
        while (i < m || j < r)//防止下标越界

            //先放到辅助数组中的肯定是小的,所以我们只需要将两边较小的放到辅助数组中就好了。
            if (j >= r || (i < m && a[i] <= a[j])) t[k++] = a[i++];
        //注意下标越界问题。
            else t[k++] = a[j++];//这里处理逆序对问题。


        for (i = l;i < r;i++) a[i] = t[i];
    }
}

int main() {
    int n = 15;

    merge_sort(0, n);
    for (int i = 0;i < n;i++) printf("%d ", a[i]);

    return 0;
}

 

 

逆序对问题    代码:

#include<stdio.h>

int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解,我将数值设为与动图一样的数值。
int t[20];//辅助数组,中转站的意思。
int ans;//逆序对数量

void merge_sort(int l, int r) {
    //如果两个数组下标相邻,就不必要再进行二分了,再分就只有一个了,无法比较了。
    if (r - l > 1) {
        int m = l + (r - l >> 1), i = l, j = m, k = l;
        //m为分开的的这一段的中间下标,i为左边起始点,j为右边起始点,k为辅助数组起始点。
        //将总的一段二分。
        merge_sort(l, m);
        merge_sort(m, r);

        //然后再将这两段归并到一起进行排序。
        while (i < m || j < r)//防止下标越界

            //先放到辅助数组中的肯定是小的,所以我们只需要将两边较小的放到辅助数组中就好了。
            if (j >= r || (i < m && a[i] <= a[j])) t[k++] = a[i++];
        //注意下标越界问题。
            else t[k++] = a[j++],ans+=m-i;//这里处理逆序对问题。


        for (i = l;i < r;i++) a[i] = t[i];
    }
}

int main() {
    int n = 15;

    merge_sort(0, n);
    printf("%d\n", ans);

    return 0;
}

 

只要你把

else t[k++] = a[j++];成else t[k++]=a[j++],ans+=m-i;就好了,记得声明ans变量。

逆序对的定义如下:对于数列的第 i 个和第 j 个元素,如果满足 i < j 且 a[i] > a[j],则其为一个逆序对;否则不是。

而else恰好符合这个条件只要有一个是从右边的数加进来的,就说明当前(左边)下标的  i到m-1都是大于这个数的。

 

五、快速排序 O(nlog(2)n)

以中间数作为基数,同时从左右边开始比较,因为基数是在中间,所以左边的数要比基数小,右边的数要比基数大,否则就交换数值,分支递归反复便得出正确的顺序。

特性:

可以处理求第几大的问题;极快,数据移动少;

缺点:

不稳定。

 

详细解析代码:

#include<stdio.h>

int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解,我将数值设为与之前一样的数值。

void quick_sort(int l, int r) {
    if (l < r) {//防止越界
        int i = l - 1, j = r + 1, x = a[l + r >> 1];
        //-1、+1的原因是因为下面我们要用++i、--j。
        //为什么不用i++、j++呢?因为我们要比较数值,要让i、j与我们比较的数值下标同步,提前+1或者-1会导致后面的交换发生错误。
        //前者是先使用i+1再将i=i+1,后者是先使用i再将i=i+1。
        while (i < j) {
            //双指针移动不符合就暂停
            while (a[++i] < x);
            while (a[--j] > x);

            //两边都不符合了,交换数值。
            if (i < j) {//学了c++后可直接用swap函数。
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        //再分治,左右两边递归排序。
        quick_sort(l, j);quick_sort(j + 1, r);
    }
}

int main() {
    int n=15;

    quick_sort(0, n - 1);
    for (int i = 0;i < n;i++) printf("%d ", a[i]);
    return 0;
}

 

寻找第k小的数    代码:

#include<stdio.h>

int a[] = { 3,44,38,5,47,15,36,26,27,2,46,4,19,50,48 };
//为了方便大家理解,我将数值设为与之前一样的数值。

int quick_sort(int l, int r, int k) {
    if (l == r) return a[l];
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    //-1、+1的原因是因为下面我们要用++i、--j。
    //为什么不用i++、j++呢?因为我们要比较数值,要让i、j与我们比较的数值下标同步,提前+1或者-1会导致后面的交换发生错误。
    //前者是先使用i+1再将i=i+1,后者是先使用i再将i=i+1。
    while (i < j) {
        //双指针移动不符合就暂停
        while (a[++i] < x);
        while (a[--j] > x);

        //两边都不符合了,交换数值。
        if (i < j) {//学了c++后可直接用swap函数。
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    int s = j - l + 1;//判断左边有多少数,是否包含第k个数
    //分治,不断缩小范围,直到l==r,输出答案。
    if (k <= s) return quick_sort(l, j, k);
    //k>s的话说明第K个值在右边的第k-s 个数中,那么在右边的k=k-s;
    return quick_sort(j + 1, r, k - s);
}

int main() {
    int n = 15, k = 5;

    int ans = quick_sort(0, n - 1, k);
    printf("%d \n", ans);
    return 0;
}

 

加载全部内容

相关教程
猜你喜欢
用户评论