数据结构与算法——冒泡排序、选择排序和快速排序

忘是亡心i 2022-08-24 11:58 232阅读 0赞

## 冒泡排序 ##

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的步骤：

1.  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.  针对所有的元素重复以上的步骤，除了最后一个。
4.  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

![SouthEast][]

/*********冒泡排序*********/
    void Bubble_sort(int arr[],int len)
    {
        int i,j;
        int temp;
        for(i=0;i<len-1;i++)
            for(j=0;j<len-i-1;j++)
            if(arr[j]>arr[j+1])
            SWAP(arr[j],arr[j+1],temp);
    }

冒泡排序的递归实现：

/** 冒泡排序的递归实现 */
    
    void Bubble_sort(int arr[], int len)
    {
        int i;
        int temp;
        if(len > 1)
        {
            for(i = 0; i < len -1; i++)
                if(arr[i] > arr[i+1])
                    SWAP(arr[i], arr[i+1], temp);
            Bubble_sort(arr, len-1);
        }
    }

冒泡排序的优化实现：

如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个flag做标记，默认为false，如果发生交互则置为true，每轮结束时检测flag，如果为true则继续，如果为false则返回；

void Bubble_sort(int arr[], int len)
    {
        int temp;
        int i, j;
    
        bool flag = true;/* flag值若为true表示需要进行比较，否则不需要继续进行比较操作 */
        for(i = 0; i < len-1 && flag == true; i++)
        {
            flag = false;
            for(j = 0; j < len-i-1; j++)
            {
                if(arr[j] > arr[j+1])
                {
                    SWAP(&arr[j], &arr[j+1], temp);
                    flag = true;
                }
            }
        }
    }

## 选择排序 ##

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

![SouthEast 1][]

/********选择排序*******/
    /**基本思想：每一趟在n-i+1个记录中选择关键字最小的记录作为有序序列中第i个记录**/
    /**每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，
    直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。**/
    void Select_sort(int arr[],int len)
    {
        int i,j;
        int min,temp;
        for(i=0;i<len-1;i++)
        {
            min=i;
            for(j=i+1;j<len;j++)
                if(arr[min]>arr[j])
                min=j;
            if(min!=i)
                SWAP(arr[i],arr[min],temp);
        }
    }

## 快速排序 ##

快速排序是冒泡排序的一种改进，冒泡排序排完一趟是最大值冒出来了，那么可不可以先选定一个值，然后扫描待排序序列，把小于该值的记录和大于该值的记录分成两个单独的序列，然后分别对这两个序列进行上述操作。这就是快速排序，我们把选定的那个值称为枢纽值，如果枢纽值为序列中的最大值，那么一趟快速排序就变成了一趟冒泡排序。所以枢纽值的选取相当重要，一般取待排序列第一个元素、中央元素和最后元素三个中的中间值，这样时间复杂度会比较好。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。  
 步骤为：

1.  从数列中挑出一个元素，称为 "基准"（pivot），
2.  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
4.  递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

/********快速排序*********/
    /*** 实现思想
        快速排序的基本思想如下：
    
        1、从待排序列中任选一个元素作为枢轴；
    
        2、将序列中比枢轴大的元素全部放在枢轴的右边，比枢轴小的元素全部放在其左边；
    
        3、以枢轴为分界线，对其两边的两个子序列重复执行步骤1和2中的操作，直到最后每个子序列中只有一个元素。
    ****/
    int Partition(int *arr,int low,int high)
    {
        int pivot;
        //temp=arr[low];
        pivot=arr[low];
        while(low<high)
        {
            while(low<high && arr[high]>=pivot)high--;
            if(low < high)
                arr[low++]=arr[high];
            while(low<high && arr[low]<=pivot)low++;
            if(low < high)
                arr[high--]=arr[low];
        }
        arr[low]=pivot;
        return low;
    }
    void Quick_sort(int *arr,int low,int high)
    {
        int pivotloc;
        if(low<high)
        {
            pivotloc=Partition(arr,low,high);
            Quick_sort(arr,low,pivotloc-1);
            Quick_sort(arr,pivotloc+1,high);
        }
    }

[SouthEast]: /images/20220823/074825108af9445580e9e4ec0ae75bd6.png
[SouthEast 1]: /images/20220823/72b3a7b72ad840b18ba98f6e8be95c5b.png