排序——交换类排序

蔚落 2021-11-11 07:52 339阅读 0赞

## 冒泡排序 ##

> **算法思想：数组中第一个元素和第二个元素比较，按照规则进行交换，再让第二个和第三个进行比较，直到最大或最小的那个数交换到最后，一趟冒泡排序完成。以升序为例，冒泡排序主要是让大的下沉，小的上浮，每一趟排序确立一个当前无序序列中最大的那个数，使之下沉。**
> 
> **时间复杂度分析：**
> 
> **                     最坏：整个数组逆序，最内层循环的语句执行（n-1+1)(n-1)/2 = n(n-1)/2   ==>   O(n^2)**
> 
> **                     最好：数组有序，O(n)**
> 
> **                     平均：O(n^2)**
> 
> **空间复杂度：O(1)**

**代码：**

void Bubble_sort(int arr[],int n)       //冒泡排序
    {
        int i,j,temp;
        for(i=0; i<n-1; i++)        //外循环为排序趟数，n个数进行n-1趟
        {
            for(j=0; j<n-i-1; j++)  //内循环为每躺比较的次数，第i躺比较n-i趟
            {
                if(arr[j]>arr[j+1])   //交换操作
                {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

## **快速排序** ##

> **算法思想：通过多次划分操作实现排序。以升序为例，每一趟选择当前所有子序列中的一个关键字（通常是第一个）为枢轴，将子序列中比枢轴小的放在枢轴前面，比枢轴大的放在枢轴后面。每一趟划分会得到多组更短的子序列，它们为下一趟划分的初始序列。**
> 
> **时间复杂度分析：**
> 
> **空间复杂度：O(log2n)，快速排序是递归进行的，需要栈的辅助**
> 
>  *  **最好为O(nlog2n)，待排序列越接近无序，效率越高**
>  *  **最坏为O(n^2)，待排序列越接近有序，效率越低**
>  *  **平均为O(nlog2n)**
>  *  **快速排序的排序趟数和初始序列有关**

**代码：**

void Quick_sort(int arr[],int low,int high)     //快速排序
    {
        int i,j,temp;
        i = low;j = high;
        if(low<high)
        {
            temp = arr[low];            //选取枢轴
            //完成一趟排序后，将数组中小于temp的值放在左边，大于temp的值放在右边
            while(i<j)
            {
                while(j>i&&arr[j]>temp) --j;  //从右往左进行扫描，找到一个小于temp的值，记录下标
                if(i<j)
                {
                    arr[i] = arr[j];        //将找到的值放在temp左边
                    ++i;                    //i右移一位
                }
                while(j>i&&arr[i]<temp) ++i;    //从左往右扫描，找到一个大于temp的值，记录下标
                if(i<j)
                {
                    arr[j] = arr[i];        //将找到的值放在temp右边
                    --j;                    //此时j左移一位
                }
            }
            arr[i] = temp;                  //将temp放在最终位置
            Quick_sort(arr,low,i-1);        //继续对temp左边进行快速排序
            Quick_sort(arr,i+1,high);       //对temp右边进行快速排序
        }
    }

**完整代码：**

#include <stdio.h>
    #include <stdlib.h>
    void Bubble_sort(int arr[],int n)       //冒泡排序
    {
        int i,j,temp;
        for(i=0; i<n-1; i++)        //外循环为排序趟数，n个数进行n-1趟
        {
            for(j=0; j<n-i-1; j++)  //内循环为每躺比较的次数，第i躺比较n-i趟
            {
                if(arr[j]>arr[j+1])   //交换操作
                {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    void Quick_sort(int arr[],int low,int high)     //快速排序
    {
        int i,j,temp;
        i = low;j = high;
        if(low<high)
        {
            temp = arr[low];            //选取枢轴
            //完成一趟排序后，将数组中小于temp的值放在左边，大于temp的值放在右边
            while(i<j)
            {
                while(j>i&&arr[j]>temp) --j;  //从右往左进行扫描，找到一个小于temp的值，记录下标
                if(i<j)
                {
                    arr[i] = arr[j];        //将找到的值放在temp左边
                    ++i;                    //i右移一位
                }
                while(j>i&&arr[i]<temp) ++i;    //从左往右扫描，找到一个大于temp的值，记录下标
                if(i<j)
                {
                    arr[j] = arr[i];        //将找到的值放在temp右边
                    --j;                    //此时j左移一位
                }
            }
            arr[i] = temp;                  //将temp放在最终位置
            Quick_sort(arr,low,i-1);        //继续对temp左边进行快速排序
            Quick_sort(arr,i+1,high);       //对temp右边进行快速排序
        }
    }
    int main()
    {
        int i;
        int arr[] = {56,12,78,34,10,90,23,67,56,43};
    //    Bubble_sort(arr,10);
        Quick_sort(arr,0,9);
        for(i=0; i<10; i++)
        {
            printf("%d\t",arr[i]);
        }
    }