算法基础（常见排序）

简单排序（冒泡&选排）

选择排序

选排原理

选择排序是一种比较简单直观的排序算法，估计也是很多人接触的第一个排序算法；它的思想原理是：

首先在未排序的数列中找到最小（或最大）的元素，然后将其放在其实位置；接着再从剩余的无排序的的元素中继续寻找最小（或最大）的元素，然后放到已排序列的末尾。以此类推，直到所有元素排序完毕

选排演示

选排.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]);
}

冒泡排序

冒泡原理

冒泡：以此比较相邻的两个元素，使越来越小（越来越大）的数据慢慢‘浮’至数据顶端，如同 就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

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

冒泡演示

冒泡.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]);
 }

进阶排序（快排&归并）

快速排序

快排原理

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

1. 首先设定一个分界值(可以为数组中的任意一个数，大部分采用首、尾或中间数)，以给该分界值将其数组分成两部分
2. 然后将大于或等于分界值的数集中到该分界值的右面，小于或等于分界值的数集中到该分界值的左面，此时数组右面都是大于或等于该分界值的数，左面都是小于等于该分界值的数。
3. 然后，对左右两边独立按照上述步骤处理，及在数组左半部分在选择一个分界值，然后将左半部分小于或等于分界值的数放到分界值放到分界值的左面，将大于等于分界值的数放到分界值的右面，数组的右侧也按这样的方法处理，
4. 递归重复上述过程，即可完成对数组的排序。

快排演示

假设对q={5 ,8 , 9, 6, 4, 5, 3, 7, 6}升序进行排序（小标从0开始）

• 此时i=0,j=8设分界值ref=5；从后往前找，第一个比5小的数是q[6]=3，因此数组更新：3 8 9 6 4 5 5 7 6
• 此时 i=0,j=6，从前往后找，第一个比5大的数是q[1]=8，因此数组更新为：3 5 9 6 4 5 8 7 6
• 此时i=1,j=6，从后往前找，第一个比5小的数是去q[4]=4，因此数组更新为：3 4 9 6 5 5 8 7 6
• 此时i=1,j=4，从前往后找，第一个比5大的数是去q[2]=9，因此数组更新为：3 4 5 6 9 5 8 7 6
• 此时i=2,j=4，从后往前找，没有比5小的数，因此数组不更新：3 4 5 6 9 5 8 7 6
• 此时i=2,j=2，不满足条件，跳出循环，此时以ref=5为分界值将原数组分为左右两部分，左半部分为小于等于5的数，右半部分为大于等于5的数， 对于前后两部分数，可以采用同样的方法来排序。

快排代码

#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]);
 } 

归并排序

归并原理

归并排序是建立在归并操作上 一种采用分治法的一种稳定的排序算法，其工作原理为：

1. 申请额外的空间，其额外空间要与要排序序列所占空间相同， 该空间用来存放合并后的序列
2. 设定两个指针，其最初位置分别为两个序列的起始位置。
3. 比较两个指针所指向的元素，选择相对小的（或大的）元素放到合并空间，并移动指针至下一位置。
4. 重复步骤3直到某一指针指到队尾，然后将剩下的所有元素，直接复制到队尾。

归并图解

归并排序.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]);
 }