C语言排序总结

柔情只为你懂 2022-06-01 01:46 183阅读 0赞

> **1.冒泡排序（Bubble Sort）**

1.1 冒泡排序原理   
冒泡排序是最简单的排序算法了，它的想法也很简单，如果是从小到达排序的话，就是每次比较两个元素，看他们的顺序有没有错，如果错了就换过来。   
![这里写图片描述][SouthEast]

1.2 冒泡排序算法步骤   
A：比较两个元素，如果第一个比第二个大，则两个元素交换位置   
B：对每一对相邻的元素做同样的工作，从第一对到最后一对。这一次执行完，最后一个元素是最大的元素。   
C：除了最后一个元素之外，对其余元素做同样的操作   
D：重复以上A，B，C三步，直到每个元素都不需要交换位置为止

1.3 算法实现

/*--------------------冒泡排序---------------------*/

void bubleSort(int data\[\], int n)  
\{   
    int i,j,temp;  
    //两个for循环，每次取出一个元素跟数组的其他元素比较  
    //将最大的元素排到最后。  
    for(j=0; j<n-1; j++)  
    \{   
        //外循环一次，就排好一个数，并放在后面，  
        //所以比较前面n-j-1个元素即可  
        for(i=0; i<n-j-1; i++)  
        \{   
            if(data\[i\]>data\[i+1\])  
            \{   
                temp = data\[i\];  
                data\[i\] = data\[i+1\];  
                data\[i+1\] = temp;  
            \}  
        \}  
    \}  
\}

1.4 算法效率

冒泡排序在所有数据都是正序的时候，最快（都排好序了，目的已达到）。当所有数据都排反序的时候最慢（用for循环反序输出就OK了）。

> ##### **2.选择排序** #####

2.1 选择排序原理   
第一遍循环找到最小的元素放到第一位，第二次循环找到一个第二小元素，放到第二位，以此完成排序。在每次循环中，先把第一个元素标记为最小元素，然后将它与其后面的元素比较，发现比它小的，就将其标记为本次循环的最小元素。   
![这里写图片描述][SouthEast 1]   
无论什么数据进入，时间复杂度都是O(n2),因此，这个排序算法适用于小数据集。

2.2 算法步骤   
A：先从未排序序列中找到最小（大）元素放到起始位置   
B：再从剩余未排序序列中继续寻找最小（大）元素放到已排序末位   
C：重复以上两步，直到排序完成

2.3 算法实现

/*--------------------选择排序---------------------*/
    void selectSort(int data[], int n)
    {
        int i,j,mix,temp;
        //每次循环数组，找出最小的元素，放在前面，前面的即为排序好的
        for(i=0; i<n-1; i++)
        {
            //假设最小元素的下标
            int mix = i;
            //将上面假设的最小元素与数组比较，交换出最小的元素的下标
            for(j=i+1; j<n; j++)
            {
                if(data[j] < data[mix])
                {
                    mix = j;
                }
            }
            //若数组中真的有比假设的元素还小，就交换
            if(i != mix)
            {
                temp = data[i];
                data[i] = data[mix];
                data[mix] = temp;
            }
        }
    }

> **3.插入排序**

3.1 插入排序原理   
只要打过扑克牌的人应该都能非常好的理解插入排序。它的原理是通过构建有序序列，对与未排序序列，从后向前扫描，逐个比较之后，插入到相应的位置上。   
![这里写图片描述][SouthEast 2]

3.2 算法步骤   
A：将第一待排序序列的第一个元素看成有序序列，将第二个元素到最后一个元素当成未排序序列   
B：从头到尾扫描未排序序列，将其插到已排序序列的的适当位置（如果两个元素相等，则插入到已排序序列元素的后面）。

3.3 算法实现

/*--------------------插入排序---------------------*/
    void bInsertSort(int data[], int n)
    {
        int low,high,mid;
        int temp,i,j;
        for(i=1; i<n; i++)
        {
            low = 0;
            //把data[i]元素插入到它的前面data[0-(i-1)]中
            temp =data[i];
            high = i-1;
            //该while是折半，缩小data[i]的范围(优化手段)
            while(low <= high)
            {
                mid = (low+high)/2;
                if(data[mid] > temp)
                {
                    high = mid-1;
                }
                else
                {
                    low = mid+1;
                }
            }
            int j = i;
            //让data与已经排序好的数组的各个元素比较，小的放前面
            while((j > low) && data[j-1] > temp)
            {
                data[j] = data[j-1];
                --j;
            }
            data[low] = temp;
        }
    }

> **4.快速排序**

**4.1 快速排序原理**   
快速排序的原理就是对于一个数组，从前找一个比首元素大的元素，从后找一个比最后一个元素小的元素，然后将两个元素进行交换。  
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

![SouthEast 3][]

4.2 算法步骤   
A. 先从数列中取出一个数作为基准数。  
B. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。  
C. 再对左右区间重复第二步，直到各区间只有一个数。

4.3 算法实现

/\*--------------------快速排序---------------------\*/  
int findPos(int data\[\], int low, int high)  
\{   
    //将大于t的元素赶到t的左边，大于t的元素赶到t的右边  
    int t = data\[low\];  
    while(low < high)  
    \{   
        while(low < high && data\[high\] >= t)  
        \{   
            high--;  
        \}  
        data\[low\] = data\[high\];  
        while(low < high && data\[low\] <=t)  
        \{   
            low++;  
        \}  
        data\[high\] = data\[low\];  
    \}  
    data\[low\] = t;  
    //返回此时t在数组中的位置  
    return low;  
\}  
//在数组中找一个元素，对大于该元素和小于该元素的两个数组进行再排序  
//再对两个数组分为4个数组，再排序，直到最后每组只剩下一个元素为止  
void quickSort(int data\[\], int low, int high)  
\{   
    if(low > high)  
    \{   
        return;  
    \}  
    int pos = findPos(data, low, high);  
    quickSort(data, low, pos-1);  
    quickSort(data, pos+1, high);  
\}

[SouthEast]: /images/20220601/2bc7bfb7351f4606ac9712cbd2b67724.png
[SouthEast 1]: /images/20220601/f8407fedc3ef4a80a0e6366db99c1168.png
[SouthEast 2]: /images/20220601/694740c30abf4fb98043a4fb4d7c3819.png
[SouthEast 3]: /images/20220601/d279ef6774e44cab9d9f118ab587dc10.png