簡(jiǎn)單排序（冒泡&選排）

選擇排序

選排原理

選擇排序是一種比較簡(jiǎn)單直觀的排序算法，估計(jì)也是很多人接觸的第一個(gè)排序算法；它的思想原理是：

首先在未排序的數(shù)列中找到最?。ɑ蜃畲螅┑脑兀缓髮⑵浞旁谄鋵?shí)位置；接著再?gòu)氖Ｓ嗟臒o(wú)排序的的元素中繼續(xù)尋找最?。ɑ蜃畲螅┑脑?，然后放到已排序列的末尾。以此類推，直到所有元素排序完畢

選排演示

選排.gif

選排代碼

#include<stdio.h>
void selectionSort(int q[],int n)
{
    int i , j , min , t ;
    for( i = 0 ; i < n-1 ; i++)
    {
        min = i;
        for( j = 1 ; j < n ; j++)
            if(q[j] < q[min]) min=j;
        if(min!=i)
        {
            t = q[i];
            q[i] = q[min];
            q[min] = t;
        }
    }
}
int main()
{
    int i;
    int q[6]={20,50,40,12,54,16};
    selectionSort(q,6);
    
    for(i=0;i<6;i++)
    printf("%d  ",q[i]);
}

冒泡排序

冒泡原理

冒泡：以此比較相鄰的兩個(gè)元素，使越來(lái)越?。ㄔ絹?lái)越大）的數(shù)據(jù)慢慢‘浮’至數(shù)據(jù)頂端，如同 就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”。

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2. 對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4. 持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

冒泡演示

冒泡.gif

冒泡代碼

#include<stdio.h>
void bubbleSort(int q[], int n)
{
    int i , j , t ;
    for( i = 0 ; i < n-1 ; i ++ )
    {
        for( j = 0 ; j < n - (i+1) ; j++)
        {
            if(q[j] > q[j+1])
            {
                t = q[j];
                q[j] = q[j+1];
                q[j+1] = t;
            }
        }
    }
}
main()
{
    int q[]={3,6,4,2,11,10,5};
    int i ;
    bubbleSort(q,6);
    
    for(i=0;i<6;i++)
        printf("%d  ",q[i]);
 }

進(jìn)階排序（快排&歸并）

快速排序

快排原理

快速排序（Quick Sort）使用以分治為核心策略，其基本思想為：

1. 首先設(shè)定一個(gè)分界值(可以為數(shù)組中的任意一個(gè)數(shù)，大部分采用首、尾或中間數(shù))，以給該分界值將其數(shù)組分成兩部分
2. 然后將大于或等于分界值的數(shù)集中到該分界值的右面，小于或等于分界值的數(shù)集中到該分界值的左面，此時(shí)數(shù)組右面都是大于或等于該分界值的數(shù)，左面都是小于等于該分界值的數(shù)。
3. 然后，對(duì)左右兩邊獨(dú)立按照上述步驟處理，及在數(shù)組左半部分在選擇一個(gè)分界值，然后將左半部分小于或等于分界值的數(shù)放到分界值放到分界值的左面，將大于等于分界值的數(shù)放到分界值的右面，數(shù)組的右側(cè)也按這樣的方法處理，
4. 遞歸重復(fù)上述過(guò)程，即可完成對(duì)數(shù)組的排序。

快排演示

假設(shè)對(duì)q={5 ,8 , 9, 6, 4, 5, 3, 7, 6}升序進(jìn)行排序（小標(biāo)從0開始）

• 此時(shí)i=0,j=8設(shè)分界值ref=5；從后往前找，第一個(gè)比5小的數(shù)是q[6]=3，因此數(shù)組更新：3 8 9 6 4 5 5 7 6
• 此時(shí) i=0,j=6，從前往后找，第一個(gè)比5大的數(shù)是q[1]=8，因此數(shù)組更新為：3 5 9 6 4 5 8 7 6
• 此時(shí)i=1,j=6，從后往前找，第一個(gè)比5小的數(shù)是去q[4]=4，因此數(shù)組更新為：3 4 9 6 5 5 8 7 6
• 此時(shí)i=1,j=4，從前往后找，第一個(gè)比5大的數(shù)是去q[2]=9，因此數(shù)組更新為：3 4 5 6 9 5 8 7 6
• 此時(shí)i=2,j=4，從后往前找，沒有比5小的數(shù)，因此數(shù)組不更新：3 4 5 6 9 5 8 7 6
• 此時(shí)i=2,j=2，不滿足條件，跳出循環(huán)，此時(shí)以ref=5為分界值將原數(shù)組分為左右兩部分，左半部分為小于等于5的數(shù)，右半部分為大于等于5的數(shù)， 對(duì)于前后兩部分?jǐn)?shù)，可以采用同樣的方法來(lái)排序。

快排代碼

#include<stdio.h>
void quick_sort(int q[],int l,int r)
{
    if(l>=r) return;
    int x=q[l],i=l-1,j=r+1;
    int t;
    while(i<j)
    {
        do i++; while(q[i]<x);
        do j--; while(q[j]>x);
        if(i<j)
        {
            t=q[i];
            q[i]=q[j];
            q[j]=t;
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}
main()
{
    int q[]={2,8,9,6,4,5,3,7,6};
    int i;
    quick_sort(q,0,9-1);
    for(i=0;i<9;i++)
    printf("%d ",q[i]);
 } 

歸并排序

歸并原理

歸并排序是建立在歸并操作上 一種采用分治法的一種穩(wěn)定的排序算法，其工作原理為：

1. 申請(qǐng)額外的空間，其額外空間要與要排序序列所占空間相同， 該空間用來(lái)存放合并后的序列
2. 設(shè)定兩個(gè)指針，其最初位置分別為兩個(gè)序列的起始位置。
3. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的（或大的）元素放到合并空間，并移動(dòng)指針至下一位置。
4. 重復(fù)步驟3直到某一指針指到隊(duì)尾，然后將剩下的所有元素，直接復(fù)制到隊(duì)尾。

歸并圖解

歸并排序.jpg

歸并代碼

#include<stdio.h>

int q[8]={1,5,7,3,6,8,2,4};
int tmp[8]; 
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
main()
{
    
    int i;
    merge_sort(q,0,8-1);
    for(i=0;i<8;i++)
    printf("%d ",q[i]);
 }