c/c++排序算法-交换排序

傷城~ 2022-10-02 09:47 185阅读 0赞

### 文章目录 ###

*   *  冒泡排序
     *   *  时间复杂度
     *  冒泡排序改进版
     *  鸡尾酒排序（双向冒泡）
     *  快速排序
     *   *  基本思想
         *  时间复杂度

## 冒泡排序 ##

> 基本思想：  
> 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

#include <stdio.h>
    
    void printfarr(int *buf, unsigned int len, int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:", count);
        unsigned int i = 0;
        for (i = 0; i < len; i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    void BubbleSort1(int *arr,unsigned int len)
    {
        
        for(unsigned int i = 0;i < len - 1;i++)//把最大值移到右边
        {
        
            for(unsigned int j = 0;j < len - i - 1;j++)
            {
        
                if(arr[j] > arr[j+1])
                {
        
                    arr[j+1] = arr[j+1] ^ arr[j];
                    arr[j] = arr[j+1] ^ arr[j];
                    arr[j+1] = arr[j+1] ^ arr[j];
                }
                printfarr(arr,len,i);
            }
        }
    }
    
    void BubbleSort2(int *arr,unsigned int len)
    {
        
        for(unsigned int i = 0;i < len - 1;i++)//把最小值移到左边
        {
        
            for(unsigned int j = i + 1;j < len;j++)
            {
        
                if(arr[i] > arr[j])
                {
        
                    arr[i] = arr[i] ^ arr[j];
                    arr[j] = arr[i] ^ arr[j];
                    arr[i] = arr[i] ^ arr[j];
                }
                printfarr(arr,len,i);
            }
        }
    }
    
    int main()
    {
        
        int arr[] = {
        9,8,7,6,5,4,3,2,1,0};
        BubbleSort2(arr,sizeof(arr)/sizeof(arr[0]));
        return 0;
    }

第一种运行结果：
    0:8 9 7 6 5 4 3 2 1 0
    0:8 7 9 6 5 4 3 2 1 0
    0:8 7 6 9 5 4 3 2 1 0
    0:8 7 6 5 9 4 3 2 1 0
    0:8 7 6 5 4 9 3 2 1 0
    0:8 7 6 5 4 3 9 2 1 0
    0:8 7 6 5 4 3 2 9 1 0
    0:8 7 6 5 4 3 2 1 9 0
    0:8 7 6 5 4 3 2 1 0 9
    1:7 8 6 5 4 3 2 1 0 9
    1:7 6 8 5 4 3 2 1 0 9
    1:7 6 5 8 4 3 2 1 0 9
    1:7 6 5 4 8 3 2 1 0 9
    1:7 6 5 4 3 8 2 1 0 9
    1:7 6 5 4 3 2 8 1 0 9
    1:7 6 5 4 3 2 1 8 0 9
    1:7 6 5 4 3 2 1 0 8 9
    2:6 7 5 4 3 2 1 0 8 9
    2:6 5 7 4 3 2 1 0 8 9
    2:6 5 4 7 3 2 1 0 8 9
    2:6 5 4 3 7 2 1 0 8 9
    2:6 5 4 3 2 7 1 0 8 9
    2:6 5 4 3 2 1 7 0 8 9
    2:6 5 4 3 2 1 0 7 8 9
    3:5 6 4 3 2 1 0 7 8 9
    3:5 4 6 3 2 1 0 7 8 9
    3:5 4 3 6 2 1 0 7 8 9
    3:5 4 3 2 6 1 0 7 8 9
    3:5 4 3 2 1 6 0 7 8 9
    3:5 4 3 2 1 0 6 7 8 9
    4:4 5 3 2 1 0 6 7 8 9
    4:4 3 5 2 1 0 6 7 8 9
    4:4 3 2 5 1 0 6 7 8 9
    4:4 3 2 1 5 0 6 7 8 9
    4:4 3 2 1 0 5 6 7 8 9
    5:3 4 2 1 0 5 6 7 8 9
    5:3 2 4 1 0 5 6 7 8 9
    5:3 2 1 4 0 5 6 7 8 9
    5:3 2 1 0 4 5 6 7 8 9
    6:2 3 1 0 4 5 6 7 8 9
    6:2 1 3 0 4 5 6 7 8 9
    6:2 1 0 3 4 5 6 7 8 9
    7:1 2 0 3 4 5 6 7 8 9
    7:1 0 2 3 4 5 6 7 8 9
    8:0 1 2 3 4 5 6 7 8 9
    第二种运行结果：
    0:8 9 7 6 5 4 3 2 1 0
    0:7 9 8 6 5 4 3 2 1 0
    0:6 9 8 7 5 4 3 2 1 0
    0:5 9 8 7 6 4 3 2 1 0
    0:4 9 8 7 6 5 3 2 1 0
    0:3 9 8 7 6 5 4 2 1 0
    0:2 9 8 7 6 5 4 3 1 0
    0:1 9 8 7 6 5 4 3 2 0
    0:0 9 8 7 6 5 4 3 2 1
    1:0 8 9 7 6 5 4 3 2 1
    1:0 7 9 8 6 5 4 3 2 1
    1:0 6 9 8 7 5 4 3 2 1
    1:0 5 9 8 7 6 4 3 2 1
    1:0 4 9 8 7 6 5 3 2 1
    1:0 3 9 8 7 6 5 4 2 1
    1:0 2 9 8 7 6 5 4 3 1
    1:0 1 9 8 7 6 5 4 3 2
    2:0 1 8 9 7 6 5 4 3 2
    2:0 1 7 9 8 6 5 4 3 2
    2:0 1 6 9 8 7 5 4 3 2
    2:0 1 5 9 8 7 6 4 3 2
    2:0 1 4 9 8 7 6 5 3 2
    2:0 1 3 9 8 7 6 5 4 2
    2:0 1 2 9 8 7 6 5 4 3
    3:0 1 2 8 9 7 6 5 4 3
    3:0 1 2 7 9 8 6 5 4 3
    3:0 1 2 6 9 8 7 5 4 3
    3:0 1 2 5 9 8 7 6 4 3
    3:0 1 2 4 9 8 7 6 5 3
    3:0 1 2 3 9 8 7 6 5 4
    4:0 1 2 3 8 9 7 6 5 4
    4:0 1 2 3 7 9 8 6 5 4
    4:0 1 2 3 6 9 8 7 5 4
    4:0 1 2 3 5 9 8 7 6 4
    4:0 1 2 3 4 9 8 7 6 5
    5:0 1 2 3 4 8 9 7 6 5
    5:0 1 2 3 4 7 9 8 6 5
    5:0 1 2 3 4 6 9 8 7 5
    5:0 1 2 3 4 5 9 8 7 6
    6:0 1 2 3 4 5 8 9 7 6
    6:0 1 2 3 4 5 7 9 8 6
    6:0 1 2 3 4 5 6 9 8 7
    7:0 1 2 3 4 5 6 8 9 7
    7:0 1 2 3 4 5 6 7 9 8
    8:0 1 2 3 4 5 6 7 8 9

### 时间复杂度 ###

T ( n ) = O ( n 2 ) T(n) = O(n^2) T(n)=O(n2)  
假设被排序的数列中有N个数。遍历一趟的时间复杂度是 O ( n ) O(n) O(n)，需要遍历多少次呢？ n − 1 n-1 n−1次！因此，冒泡排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2)

## 冒泡排序改进版 ##

添加一个标记，如果一趟遍历中发生了交换，则标记为true，否则为false。如果某一趟没有发生交换，说明排序已经完成！

#include <stdio.h>
    
    void printfarr(int *buf, unsigned int len, int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:", count);
        unsigned int i = 0;
        for (i = 0; i < len; i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    void BubbleSort(int *arr,unsigned int len)
    {
        
        for(unsigned int i = 0;i < len - 1;i++)//把最大值移到右边
        {
        
            int flag = 0;
            for(unsigned int j = 0;j < len - i - 1;j++)
            {
        
                if(arr[j] > arr[j+1])
                {
        
                    arr[j+1] = arr[j+1] ^ arr[j];
                    arr[j] = arr[j+1] ^ arr[j];
                    arr[j+1] = arr[j+1] ^ arr[j];
                    flag = 1;
                }
                printfarr(arr,len,i);
            }
            if(flag == 0)
            {
        
                break;
            }
        }
    }
    
    int main()
    {
        
        int arr[] = {
        1,0,2,3,8,6,9,7};
        BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));
        return 0;
    }

运行结果：
    0:0 1 2 3 8 6 9 7
    0:0 1 2 3 8 6 9 7
    0:0 1 2 3 8 6 9 7
    0:0 1 2 3 8 6 9 7
    0:0 1 2 3 6 8 9 7
    0:0 1 2 3 6 8 9 7
    0:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 8 7 9
    1:0 1 2 3 6 7 8 9
    2:0 1 2 3 6 7 8 9
    2:0 1 2 3 6 7 8 9
    2:0 1 2 3 6 7 8 9
    2:0 1 2 3 6 7 8 9
    2:0 1 2 3 6 7 8 9

## 鸡尾酒排序（双向冒泡） ##

鸡尾酒排序的元素比较和交换过程是双向的

#include <stdio.h>
    
    void printfarr(int *buf, unsigned int len, int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:", count);
        unsigned int i = 0;
        for (i = 0; i < len; i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    void BubbleSort(int *arr,unsigned int len)
    {
        
        for(unsigned int i = 0;i < len / 2 - 1;i++)
        {
        
            int flag = 0;
            for(unsigned int j = i;j < len - i - 1;j++)//奇数轮
            {
        
                if(arr[j] > arr[j+1])
                {
        
                    arr[j+1] = arr[j+1] ^ arr[j];
                    arr[j] = arr[j+1] ^ arr[j];
                    arr[j+1] = arr[j+1] ^ arr[j];
                    flag = 1;
                }
                printfarr(arr,len,i);
            }
            if(flag == 0)
            {
        
                break;
            }
            for(unsigned int j = len - i - 1;j > i;j--)//偶数轮
            {
        
                if(arr[j] < arr[j-1])
                {
        
                    arr[j-1] = arr[j-1] ^ arr[j];
                    arr[j] = arr[j-1] ^ arr[j];
                    arr[j-1] = arr[j-1] ^ arr[j];
                    flag = 1;
                }
                printfarr(arr,len,i);
            }
            if(flag == 0)
            {
        
                break;
            }
        }
    }
    
    int main()
    {
        
        int arr[] = {
        2,3,4,5,6,7,8,1};
        BubbleSort(arr,sizeof(arr)/sizeof(arr[0]));
        return 0;
    }

运行结果：
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 8 1
    0:2 3 4 5 6 7 1 8
    0:2 3 4 5 6 7 1 8
    0:2 3 4 5 6 1 7 8
    0:2 3 4 5 1 6 7 8
    0:2 3 4 1 5 6 7 8
    0:2 3 1 4 5 6 7 8
    0:2 1 3 4 5 6 7 8
    0:1 2 3 4 5 6 7 8
    1:1 2 3 4 5 6 7 8
    1:1 2 3 4 5 6 7 8
    1:1 2 3 4 5 6 7 8
    1:1 2 3 4 5 6 7 8
    1:1 2 3 4 5 6 7 8

这就是鸡尾酒排序的思路。排序过程就像钟摆一样，第一轮从左到右，第二轮从右到左，第三轮再从左到右…  
代码外层的大循环控制着所有排序回合，大循环内包含两个小循环，第一个循环从左向右比较并交换元素，第二个循环从右向左比较并交换元素。

## 快速排序 ##

### 基本思想 ###

> 1）选择一个基准元素,通常选择第一个元素或者最后一个元素,  
> 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。  
> 3）此时基准元素在其排好序后的正确位置  
> 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

一趟排序的过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70]  
排序全过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70 1]

#include <stdio.h>
    
    void printfarr(int *buf, unsigned int len, int count)
    {
        
        if (buf == NULL)
        {
        
            return;
        }
        printf("%d:", count);
        unsigned int i = 0;
        for (i = 0; i < len; i++)
        {
        
            printf("%d ", buf[i]);
        }
        printf("\n");
    }
    
    unsigned int partition(int *arr,unsigned int len,unsigned int low,unsigned int high)
    {
        
        int privotKey = arr[low];//基准元素
        printf("privotKey = %d\n",privotKey);
        while(low < high)
        {
        
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while(low < high && arr[high] >= privotKey)
            {
        
                --high;
            }
            // 如果队尾元素小于privotKey了,需要将其赋值给low
            arr[low] = arr[high];
            // 当队首元素小于等于privotKey时,向前挪动low指针
            while(low < high && arr[low] <= privotKey)
            {
        
                ++low;
            }
            arr[high] = arr[low];
            printfarr(arr,len,0);
        }
        arr[low] = privotKey;
        printfarr(arr,len,1);
        return low;
    }
    
    void QuickSort(int *arr,unsigned int len,unsigned int low,unsigned int high)
    {
        
        if(low < high)
        {
        
            unsigned int privotLocation = partition(arr,len,low,high);
            QuickSort(arr,len,low,privotLocation - 1);
            QuickSort(arr,len,privotLocation + 1,high);
        }
    }
    
    int main()
    {
        
        int arr[] = {
        3,1,5,7,2,4,9,6,10,8};
        unsigned int len = sizeof(arr)/sizeof(arr[0]);
        unsigned int low = 0;
        unsigned int high = len - 1;
        QuickSort(arr,len,low,high);
        return 0;
    }

运行结果:
    privotKey = 3
    0:2 1 5 7 5 4 9 6 10 8
    0:2 1 5 7 5 4 9 6 10 8
    1:2 1 3 7 5 4 9 6 10 8
    privotKey = 2
    0:1 1 3 7 5 4 9 6 10 8
    1:1 2 3 7 5 4 9 6 10 8
    privotKey = 7
    0:1 2 3 6 5 4 9 9 10 8
    0:1 2 3 6 5 4 9 9 10 8
    1:1 2 3 6 5 4 7 9 10 8
    privotKey = 6
    0:1 2 3 4 5 4 7 9 10 8
    1:1 2 3 4 5 6 7 9 10 8
    privotKey = 4
    0:1 2 3 4 5 6 7 9 10 8
    1:1 2 3 4 5 6 7 9 10 8
    privotKey = 9
    0:1 2 3 4 5 6 7 8 10 10
    0:1 2 3 4 5 6 7 8 10 10
    1:1 2 3 4 5 6 7 8 9 10

### 时间复杂度 ###

最好的情况  
 T ( n ) = O ( n l o g n ) T(n) = O(nlogn) T(n)=O(nlogn)  
最坏的情况  
 T ( n ) = O ( n 2 ) T(n) = O(n^2) T(n)=O(n2)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70]: /images/20220113/cec4c398efbb44cea67a54eee0f24c1c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JfTmVtbw_size_16_color_FFFFFF_t_70 1]: /images/20220113/9c0f6158a94a400d9214f9087c0de625.png