冒泡排序、快速排序--C语言

柔光的暖阳◎ 2022-04-02 12:42 271阅读 0赞

排序算法分为内部排序和外部排序，内部排序又分为交换排序、选择排序、插入排序。今天写一下交换排序的算法。  
  交换排序的思想是比较两个对象的关键字，如果这两个对象的关键字发生逆序，则交换这两个对象的位置。交换排序分为冒泡排序和快速排序。  
  对于冒泡排序：如果待排序的元素有n个，则要进行n-1轮比较，第i轮的比较次数为n-i-1次。对于冒泡排序算法的改进则是增加一个bool类型的变量，用于记录第i轮是否发生过元素交换，如果没有发生过元素交换，则排序算法结束，元素已经有序，否则要进行下一轮。

冒泡排序代码如下：

//冒泡排序
    void bubbleSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        int temp = 0;//中间变量，用于进行两个数的交换
        bool sig = false;//标志位，如果经过某一轮比较，没有数字进行交换，说明当前数组已经是有序的，不用再进行剩余的比较
        for(i = 0;i < len;i++)
        {
        
            sig = false;
            for(j = 0;j < len - i - 1;j++)
            {
        
                if(arr[j + 1] < arr[j])
                {
        
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    sig = true;
                }
            }
            if(!sig)
            {
        
                break;
            }
        }
    }

对于快速排序（从大到小排序），其基本原理是：随机选取一个元素作为枢纽元素，将所有大于枢纽元素的元素放到枢纽元素的右边，将所有小于或等于该枢纽元素的元素放到该枢纽元素的左边；此时，枢纽元素的最终位置已经确定，而数组被分为两部分，其中一部分元素均比枢纽元素的值大，另一部分的元素均不大于枢纽元素，对被分为两部分的元素重复上述过程，直到所有元素都在最终位置上。  
  代码的设计是首先选取第一个元素作为枢纽元素（其中0下标位置用于存放枢纽元素），之后分别将被分为两部分的元素的第一个元素作为枢纽元素重复上述过程。

快速排序算法代码如下：

//快速排序,a[0]用于存放枢纽元素
    void QuikSort(int *arr,int m,int n)
    {
        
        if(m >= n)
        {
        
            return;
        }
        int low = m;
        int high = n;
        arr[0] = arr[low];
        while(low < high)
        {
        
            while(arr[high] > arr[0] && high > low)
            {
        
                high --;
            }
            arr[low] = arr[high];
            while(arr[low] <= arr[0] && low < high)
            {
        
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = arr[0];//枢纽元素的最终位置
        QuikSort(arr,m,low - 1);
        QuikSort(arr,low + 1,n);
    }

今天写完快速排序的算法后，突然有了点自信。之前不敢投简历一直觉得自己没有准备好，排序算法还没有看，查找相关的知识点还没有复习，图的内容也忘的差不多了。。。好多理由，同时也是好多借口。总觉得知识没有在自己脑子里，其实只是自己不愿意认真思考的一个借口。今天自己没有看书，没有找ppt，凭借着自己之前的记忆与理解写出了快速排序的算法，虽然代码写的不是特别好，但是至少证明快速排序算法的理论和冒泡排序的理论自己还是知道，它们已经深深印在自己脑子里，只是自己没有去查找它们而已。不要觉得自己学过的东西必须经过再次看书复习才能知道，其实只要自己稍微思考一下，唤起自己的记忆，很多东西自己是没有忘记的！  
  没有准备好只是自己给自己的懒惰和害怕找的借口而已。多动脑，多思考，多动手，坚信自己是最棒的！要不然自己的一生都要为这个“没有准备好”的借口买单了。实践出真知，行动才有可能，在那里空想没有一点帮助，反而会增加自己的焦虑感！  
今天有点啰嗦了，只是自己感慨颇多～～～最后把所有的代码一并附上吧～

#include <stdio.h>
    
    //冒泡排序
    void bubbleSort(int *arr,int len)
    {
        
        int i = 0;
        int j = 0;
        int temp = 0;//中间变量，用于进行两个数的交换
        bool sig = false;//标志位，如果经过某一轮比较，没有数字进行交换，说明当前数组已经是有序的，不用再进行剩余的比较
        for(i = 0;i < len;i++)
        {
        
            sig = false;
            for(j = 0;j < len - i - 1;j++)
            {
        
                if(arr[j + 1] < arr[j])
                {
        
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    sig = true;
                }
            }
            if(!sig)
            {
        
                break;
            }
        }
    }
    
    //快速排序,a[0]用于存放枢纽元素
    void QuikSort(int *arr,int m,int n)
    {
        
        if(m >= n)
        {
        
            return;
        }
        int low = m;
        int high = n;
        arr[0] = arr[low];
        while(low < high)
        {
        
            while(arr[high] > arr[0] && high > low)
            {
        
                high --;
            }
            arr[low] = arr[high];
            while(arr[low] <= arr[0] && low < high)
            {
        
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = arr[0];//枢纽元素的最终位置
        QuikSort(arr,m,low - 1);
        QuikSort(arr,low + 1,n);
    }
    
    int main()
    {
        
        int i = 0;
        int arr[5] = {
        6,3,8,5,2};
        printf("Before bubble sort arr:");
        for(i = 0;i < 5;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        bubbleSort(arr,5);
        printf("After bubble sort arr:");
        for(i = 0;i < 5;i++)
        {
        
            printf("%d ",arr[i]);
        }
        printf("\n");
        int arr2[9] = {
        0,20,31,15,8,38,4,52,44};
        printf("Before quick sort arr2:");
        for(i = 1;i < 9;i ++)
        {
        
            printf("%d ",arr2[i]);
        }
        printf("\n");
        QuikSort(arr2,1,8);
        printf("After quick sort arr2:");
        for(i = 1;i < 9;i ++)
        {
        
            printf("%d ",arr2[i]);
        }
        printf("\n");
        return 0;
    }