C语言排序

#include <stdio.h>

#define SWAP(x, y, type) {type temp = x; x = y; y = temp;}
//#define SWAP(x, y) {x = x+y; y = x - y; x = x - y;}

void outprint(int arr[], int n)
{
    int i = 0;
    for (; i < n; i++)
    {
        printf("arr[%d] = %d\t", i, arr[i]);
    }
    printf("\n");
}
//冒泡排序（沉底排序）
void bubble_sort(int arr[], int n)
{
    int i, j, flag;

    for (i=0; i < n-1; i++)    //最外层n-1次
    {
        flag = 1;
        for (j = 0; j < n-1-i; j++)    //每次都少一次比较(-i)
        {
            if (arr[j] > arr[j+1])
            {
                SWAP(arr[j], arr[j+1], int)
                flag = 0;
            }
        }

        if (flag == 1)
        {
            break;
        }
    }
}
//插入排序
void insert_sort(int arr[], int n)
{
    int i, j, k;
    int temp;
    for (i=0; i < n - 1; i++)
    {
        j = i+1;
        temp = arr[j];

        for (;j>0 && temp < arr[j-1]; j--)
        {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}
//选择排序
void select_sort(int arr[], int n)
{
    int i, j, min;

    for (i = 0; i < n - 1; i++)
    {
        min = i;

        for (j = i+1; j < n ; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
            }
        }

        if (min != i)
        {
            SWAP(arr[i], arr[min], int)
        }
    }
}
//选择排序改进版
void select_sort_improve(int arr[], int n)    //选择排序改进
{
    int i, j, min, max;

    for (i = 0; i < (n/2) ; i++)
    {
        min = max = i;

        for (j = i+1; j < n - i ; j++)
        {
            if (arr[j] < arr[min])
            {
                min = j;
                continue;
            }
            if (arr[j] > arr[max])
            {
                max = j;
            }
        }

        if (min != i)
        {
            SWAP(arr[min], arr[i], int)
        }

        if (max != i)
        {
            SWAP(arr[max], arr[n-1-i], int)
        }
    }
}
//快速排序
				
					
						
							点击(此处)折叠或打开
						
					
					
						int partition(int arr[], int first, int last)
{
    int temp = arr[first];

    while(first < last)
    {
        while (first < last && temp < arr[last])
        {
            last--;
        }
        if (first < last)
        {
            arr[first++] = arr[last];
        }

        while (first < last && temp > arr[first])
        {
            first++;
        }
        if (first < last)
        {
            arr[last--] = arr[first];
        }
    }
    arr[first] = temp;
    return first;
}

void quick_sort(int arr[], int first, int last)
{
    int k;
    if (first < last)
    {
        k = partition(arr, first, last);
        quick_sort(arr, first, k-1);
        quick_sort(arr, k+1, last);
    }
}

int main(int argc, char *argv[])
{
    int arr[] = {2,1,4,0,2,4,34,5,12,33};
    //int arr[] = {1, 0};
    int num = sizeof(arr)/sizeof(arr[0]);

    printf("Before Sort:\n");
    outprint(arr, num);

//    bubble_sort(arr, num);
//    insert_sort(arr, num);
//    select_sort(arr, num);
//    select_sort_improve(arr, num);
    quick_sort(arr, 0, num-1);    //传入的是元素下标

    printf("\nAfter Sort:\n");
    outprint(arr, num);
}