排序方法（冒泡、选择、插入、递归）

1.冒泡排序

#include <stdio.h>

void bubble_sort(int arr[], int n);
int main(void)
{
    int a[10] = {100, 2, 4, 1, 111, 88, 78, 98, 23, 99};

    bubble_sort(a, 10);

    for (int i = 0; i < 10; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}

//冒泡排序:从大到小 
void bubble_sort(int arr[], int n)
{
    int i,j,tmp;
    // 比较趟数
    for (i = 0; i < n-1; i ++) 
    {
        // 每一趟比较的元素索引范围
        for (j = 0; j < n-i-1; j++) 
        {
            if (arr[j] > arr[j+1])
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                /* 不用中间变量，用异或运算符进行交换
                arr[j] = arr[j] ^ arr[j+1];
                arr[j+1] = arr[j] ^ arr[j+1];
                arr[j] = arr[j] ^ arr[j+1];
                */
             }
        }
    }
}

2.选择排序

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int main()
{
    int i,j,tmp;
    int arr[MAX] = {}; 
    printf("排序前：");
    for(i=0;i<MAX;i++)
    {
        arr[i] = rand()%100;
        printf("%d ",arr[i]);
    }   
    printf("\n");

    for(i= 0; i<MAX-1; i++)
    {
        for(j= i+1; j<MAX; j++)
        {
            if(arr[i]<arr[j])
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }   
    printf("排序后：");
    for(i=0;i<MAX;i++)
    {
        printf("%d ",arr[i]);
    }   
    printf("\n");


    return 0;
}

选择排序优化

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int main()
{
    int i,j,tmp,min;
    int arr[MAX] = {}; 
    printf("排序前：");
    for(i=0;i<MAX;i++)
    {   
        arr[i] = rand()%100;
        printf("%d ",arr[i]);
    }   
    printf("\n");

    for(i= 0; i<MAX-1; i++)
    {   
        min = i;
        for(j= i+1; j<MAX; j++)
        {
            if(arr[j]<arr[min])
            {
                min = j;
            }
            if(min!=i)
            {
                tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
    }   
    printf("排序后：");
    for(i=0;i<MAX;i++)
    {   
        printf("%d ",arr[i]);
    }   
    printf("\n");
    return 0;
}

3.插入排序

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int main()
{
    int i,j,tmp;
    int arr[MAX] = {}; 
    printf("排序前：");
    for(i=0;i<MAX;i++)
    {   
        arr[i] = rand()%100;
        printf("%d ",arr[i]);
    }   
    printf("\n");

    for(i= 1; i<MAX; i++)
    {   
        tmp = arr[i];

        for(j= i-1; j>=0; j--)
        {
            if(tmp > arr[j])
            {
                arr[j+1] = arr[j];
            }
            else
                break;
        }
        arr[j+1] = tmp;
    }   
    printf("排序后：");
    for(i=0;i<MAX;i++)
    {   
        printf("%d ",arr[i]);
    }   
    printf("\n");
    return 0;
}

4.快速排序

*
 通过递归快速排序
 */
#include <stdio.h>

static  int _get_pos(int *p, int l, int r);
static void _myqsort(int *p, int l, int r);
static void myqsort(int *p, int n);

int main(void)
{
    int arr[] = {5,1,6,7,2,10,4,8,6,7};

    myqsort(arr, sizeof(arr)/sizeof(*arr));

    for (int i = 0; i < sizeof(arr)/sizeof(*arr); i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

static void myqsort(int *p, int n)
{
    _myqsort(p, 0, n-1);
}

static void _myqsort(int *p, int l, int r)
{
    int pos;

    if (l >= r)
        return;

    pos = _get_pos(p, l, r);
    _myqsort(p, 0, pos-1);
    _myqsort(p, pos+1, r);
}

/*
 根据提供的整型数组，返回标兵坐标
 */
static  int _get_pos(int *p, int l, int r)
{
    int i, j, x;

    i = l;
    j = r;
    x = p[l];// 标兵

    while (i < j) {
        while (i < j && x <= p[j])
            j --;
        if (x > p[j]) {
            p[i++] = p[j];
        }
            
        while (i < j && x >= p[i])  
            i ++;
        if (x < p[i]) {
            p[j--] = p[i];
        }
    }

    p[i] = x;

    return i;
}