快捷導(dǎo)航

C語言排序方法(冒泡,選擇,插入,歸并,快速)

更新時(shí)間：2021年08月13日 09:18:45 作者：梨花落-

這篇文章給大家分享C語言所有經(jīng)典排序方法，文章給大家提供完整的實(shí)例代碼幫助大家快速學(xué)習(xí)掌握C語言排序方法，感興趣的朋友一起看看吧

1.冒泡排序

它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。

算法步驟比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

在這里插入圖片描述

執(zhí)行過程：

# include <stdio.h>
# include <string.h>
int main(void)
{
    int arr[] = {5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
    int len= sizeof(arr) / sizeof(arr[0]);;  
    int i;  //比較的輪數(shù)
    int j;  //每輪比較的次數(shù)
    int temp;  //交換數(shù)據(jù)時(shí)用于存放中間數(shù)據(jù)
    for (i=0; i<len-1; ++i)  //比較n-1輪
    {
        for (j=0; j<len-1-i; ++j)  //每輪比較n-1-i次,
        {
            if (arr[j] < arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    printf("排序后:\n");
    for (i=0; i<len; ++i)
    {
        printf("%d\x20", arr[i]);
    }
    printf("\n");
    return 0;
}

2.選擇排序

選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。

算法步驟首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置。
再從剩余未排序元素中繼續(xù)
尋找最?。ù螅┰?，然后放到已排序序列的末尾。

重復(fù)第二步，直到所有元素均排序完畢。

請(qǐng)?zhí)砑訄D片描述

代碼：

#include <stdio.h>
# include <string.h>
int main() {
        int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
       int i, j, temp;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) { 
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
        for (i = 0; i < len; i++)
                printf("%d ", arr[i]);
        return 0;
}

3.插入排序

插入排序，一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法 [1] 。插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng) [2] 。

算法步驟將第一待排序序列第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列。
從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置。（如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。）

請(qǐng)?zhí)砑訄D片描述

#include <stdio.h>
# include <string.h>
int main(){
     int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
  int len = (int) sizeof(arr) / sizeof(*arr);
	int i,j,x; 
    for( i= 1; i<len; i++){
        if(arr[i] < arr[i-1]){//若第 i 個(gè)元素大于 i-1 元素則直接插入；反之，需要找到適當(dāng)?shù)牟迦胛恢煤笤诓迦搿?
             j= i-1;
             x = arr[i];
            while(j>-1 && x < arr[j]){  //采用順序查找方式找到插入的位置，在查找的同時(shí)，將數(shù)組中的元素進(jìn)行后移操作，給插入元素騰出空間
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = x;      //插入到正確位置
        }
}
    for(j=0; j<len; j++){
        printf("%d ",arr[j]);
    }
    printf("\n");
    return 0;
}

4.歸并排序

歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：

自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第 2 種方法）；

自下而上的迭代；

算法步驟申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；

設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；

比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；

重復(fù)步驟 3 直到某一指針達(dá)到序列尾；

將另一序列剩下的所有元素直接復(fù)制到合并序列尾。
#include <stdio.h>
#define MAXSIZE 10

// 遞歸的方式實(shí)現(xiàn)歸并排序

// 實(shí)現(xiàn)歸并，并把結(jié)果存放到list1

# include <string.h>
#include <stdio.h>
void merging(int *list1, int list1_size, int *list2, int list2_size) {
    int i,j,k, m;
    int temp[MAXSIZE];
    i = j = k = 0;
    while(i < list1_size && j < list2_size)
    {
        if(list1[i] < list2[j])
        {
            temp[k] = list1[i];
            k++;
            i++;
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }
    while(i < list1_size)
    {
        temp[k++] = list1[i++];
    }
    while(j < list2_size)
    {
        temp[k++] = list2[j++];
    }
    for(m = 0;m < (list1_size + list2_size);m++)
    {
        list1[m] = temp[m];
    } }
void MergeSort(int k[], int n) {
    if(n > 1)
    {
        /*
        *list1是左半部分，list2是右半部分
        */
        int *list1 = k;
        int list1_size = n/2;
        int *list2 = k + list1_size;
        int list2_size = n - list1_size;
        MergeSort(list1, list1_size);
        MergeSort(list2, list2_size);
        // 把兩個(gè)合在一起
        merging(list1, list1_size, list2, list2_size);
    }
}
int main() {
    int i, arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};    int len = (int) sizeof(arr) / sizeof(*arr); 
    MergeSort(arr, len);
    printf("排序后的結(jié)果是：");
    for(i = 0;i < len;i++)
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0; 
}

5.快速排序

原理:

快速排序,給基準(zhǔn)數(shù)據(jù)找其正確索引位置的過程.

如下圖所示,假設(shè)最開始的基準(zhǔn)數(shù)據(jù)為數(shù)組第一個(gè)元素23,則首先用一個(gè)臨時(shí)變量去存儲(chǔ)基準(zhǔn)數(shù)據(jù),即tmp=23;然后分別從數(shù)組的兩端掃描數(shù)組，設(shè)兩個(gè)指示標(biāo)志:low指向起始位置，high指向末尾.

如果掃描到的值大于基準(zhǔn)數(shù)據(jù)就讓high減1,如果發(fā)現(xiàn)有元素比該基準(zhǔn)數(shù)據(jù)的值小(如上圖中18<=tmp)，就將high位置的值賦值給low位置。

如果掃描到的值小于基準(zhǔn)數(shù)據(jù)就讓low加1,如果發(fā)現(xiàn)有元素大于基準(zhǔn)數(shù)據(jù)的值(如上圖46=>tmp)，就再將low位置的值賦值給high位置的值.

算法步驟從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）;

重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作；

遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序；

請(qǐng)?zhí)砑訄D片描述

#include "stdio.h"
typedef struct _Range {
    int start, end;    //開始指向分別指向兩端 
} Range;
Range new_Range(int s, int e) {
    Range r;
    r.start = s;     //開始指向需要排序數(shù)組的兩端 
    r.end = e;
    return r;   //返回一個(gè)結(jié)構(gòu)體 
}
void swap(int *x, int *y) {   //交換數(shù)據(jù)函數(shù) 
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return;    //保證數(shù)據(jù)長(zhǎng)度大于0 
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 選取中間點(diǎn)作為基準(zhǔn)點(diǎn) 
        int left = range.start, right = range.end;
        do {
            while (arr[left] < mid) ++left;   // 檢測(cè)基準(zhǔn)點(diǎn)左側(cè)是否符合要求
            while (arr[right] > mid) --right; //檢測(cè)基準(zhǔn)點(diǎn)右側(cè)是否符合要求
            if (left <= right) {
                swap(&arr[left], &arr[right]);
                left++;
                right--;               // 移動(dòng)指針以繼續(xù)
            }
        } while (left <= right);
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}
int main()
{
	int j;
	  int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
        quick_sort(arr,len);
            for(j=0; j<len; j++){
        printf("%d ",arr[j]);
    }
    printf("\n");
}