C语言常用算法排序

【1】冒泡排序（面试常问）

1、普通

//小->大
#include <stdio.h>
void bubble(int a[],int size)
{
    int i,j,temp=0;
    for(i=0;i<size-1;i++){ //比较size-1轮
        for(j=0;j<size-i-1;j++){ //每轮比较size-i-1次，-i是每轮后都会有1个数排好了，-1是两两比较，每轮比较size-1次
            if(a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }   
}
int main(int argc, const char *argv[])
{
    int i;
    int a[6] = {4,3,6,2,8,5};
    bubble(a,6);
    for(i=0;i<6;i++)
        printf("%d ",a[i]);
    putchar(10);
    return 0;
}

2、优化

//小->大
#include <stdio.h>
#include <stdbool.h>
void bubble(int a[],int size)
{
    int i,j,temp=0;
    for(i=0;i<size-1;i++){
    	bool swap = false; //假设没有交换
        for(j=0;j<size-i-1;j++){
            if(a[j] > a[j+1]){
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                swap = true; //交换了就为true
            }
        }
    	if(!swap) //交换了就(!1)，没交换就break;
            break;
    }   
}

【2】选择排序

//小->大
#include <stdio.h>
void select(int a[],int size)
{
    int i,j,k=0,temp=0;
    for(i=0;i<size-1;i++){
        k=i;
        for(j=i+1;j<size;j++){
            if(a[k] > a[j]){  //注意是a[k]和a[j]比较，a[k]大就交换
                k=j;
            }
        }
        if(k != i){ 
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }   
}
int main(int argc, const char *argv[])
{
    int i;
    int a[6] = {4,3,6,2,8,5};
    select(a,6);
    for(i=0;i<6;i++)
        printf("%d ",a[i]);
    putchar(10);
    return 0;
}

【3】归并排序

#include <stdio.h>
 
#define A_N 5
#define B_N 7
#define C_N (A_N+B_N)
int main(int argc, const char *argv[])
{
	int i = 0,j = 0,k=0;
	int a[A_N] = {1,3,5,7,9};
	int b[B_N] = {2,4,6,8,10,11,12};
	int c[C_N] = {0};
	while(i<A_N && j<B_N){
		while(a[i] < b[j] && i<A_N){
			c[k++] = a[i++];
		}
 
		while(i<A_N && a[i] > b[j] && j<B_N){
			c[k++] = b[j++];
		}
	}	
	
	while(i == A_N && j<B_N){
		c[k++] = b[j++];
	}
 
	while(j==B_N && i<A_N){
		c[k++] = a[i++];
	}
 
	for(k=0; k<C_N; k++){
		printf("%d\t",c[k]);
	}
	puts("");
 	return 0;
}

【4】快速排序

#include <stdio.h>
void quick_sort(int arr[],int left,int right)
{
	int i = left,j = right;
	int temp=0;
	int pivot;
	pivot = arr[(left + right)/2];
	while(i <= j){
		// 从左到右找到大于等于基准点的元素
		while (arr[i] < pivot)
			i++;
		// 从右到左找到小于等于基准点的元素
		while (arr[j] > pivot)
			j--;
		// 如果i <= j,则互换
		if(i <= j){
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}
	}
	if(left < j)
		quick_sort(arr,left,j);
	if(i < right)
		quick_sort(arr,i,right);
}
int main(int argc, const char *argv[])
{
	int arr[10] = {4,5,7,3,8,1,6,9,0,2};
	int i,lenth;
	lenth = sizeof(arr)/sizeof(arr[0]);
	quick_sort(arr,0,lenth-1);
	printf("排序后的结果是> ");
	for(i=0;i<lenth;i++){
		printf("%d ",arr[i]);
	}
	putchar(10);
	return 0;
}