C语言实现排序算法的六种方式_c语言排序

1、冒泡法

void Sort(int *pData,int count)
{
	int temp;
	int i,j;
	for(i=0;i<count;i++)
	{
		for(j=0;j<count-i-1;j++)
		{
           if(pData[j]>pData[j+1])
			{
			   temp=pData[j];
			   pData[j]=pData[j+1];
			   pData[j+1]=temp;
		    }
		}
	}
}


int main()
{
	int data[]={10,9,8,7,6,5,4}; 
	Sort(data,7);
	int i;
	for(i=0;i<7;i++)
	{
		printf("%d\t",data[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2、交换法 每次用当前的元素一一的同其后的元素

void Sort(int *pData,int count)
{
	int temp;
	int i,j;
	for(i=0;i<count;i++)
	{
		for(j=i+1;j<count;j++)
		{
			if(pData[j]<pData[i])
			{
				temp=pData[i];
				pData[i]=pData[j];
				pData[j]=temp;
			}
		}
	}
}

int main()
{
	int data[]={10,9,8,7,6,5,3};
	Sort(data,7);
	int i;
	for(i=0;i<7;i++)
	{
		printf("%d\t",data[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3、选择法 从数据中选择最小的同第一个值交换，在从剩下的部分中选择最小的与第二个交换，这样往复下去

void Sort(int * pData,int count)
{
	int temp;
	int pos;
	int i,j;
	for(i=0;i<count;i++)
	{
		temp=pData[i];
		pos=i;
		for(j=i+1;j<count;j++)
		{
			if(pData[j]<temp)
			{
				temp=pData[j];
				pos=j;
			}
		}
		pData[pos]=pData[i];
		pData[i]=temp;
	}
}

int main()
{
	int data[]={10,11,23,65,78,3,5};
	Sort(data,7);
	int i;
	for(i=0;i<7;i++)
	{
		printf("%d\t",data[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4、插入法
在前面的数中寻找相应的位置插入，
然后继续下一张
插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。

void Sort(int * pData,int count)
{
	int temp;
	int pos;
	int i,j;
	for(i=0;i<count;i++)
	{
		temp=pData[i];
		pos=i-1;
		while((pos>=0)&&(temp<pData[pos]))
		{
			pData[pos+1]=pData[pos];
			pos--;
		}
		pData[pos+1]=temp;
	}
}

int main()
{
	int data[]={99,34,54,23,12,76};
	Sort(data,6);
	int i;
	for(i=0;i<6;i++)
	{
		printf("%d\t",data[i]);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

5、快速排序法
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明：挖坑填数+分治法：
先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。

以一个数组作为示例，取区间第一个数为基准数。
0 1 2 3 4 5 6 7 8 9
72 6 57 88 60 42 83 73 48 85

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;

数组变为：
0 1 2 3 4 5 6 7 8 9
48 6 57 88 60 42 83 73 88 85

i = 3; j = 7; X=72

再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：
0 1 2 3 4 5 6 7 8 9
48 6 57 42 60 72 83 73 88 85

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
代码实现如下：

#include<stdio.h>
int partition(int a[],int left,int right)
{
   int x=a[left];
   while(left<right)
   	{
   	    while(right>left && a[right]>x)
   	    	{
   	    	   right--;
   	    	}
	   if(left<right)
	   	{
	   	   a[left]=a[right];
		   left++;
	   	}
	   while(left<right && a[left]<x)
	   	{ 
	   	   left++;
	   	}
	   if(left<right)
	   	{
	   	   a[right]=a[left];
		   right--;
	   	}	   	
   	}
       a[left]=x;
	return left;
}

void quikSort(int a[],int posstart,int posend)
{
     if(posstart<posend)
    	{
    	    int posmid=partition(a,posstart,posend);
            quikSort(a,posstart,posmid-1);
	        quikSort(a,posmid+1,posend);
    	}
}

void print_array(int a[],int n)
{
   int i;
   for(i=0;i<n;i++)
   	{
   	  printf("%d\t",a[i]);
   	}
   printf("\n");
}

int main()
{
  int a[] = {7, 2, 5, 6, 0, 10, 4}; 
  quikSort(a,0,sizeof(a)/sizeof(a[0])-1);
  print_array(a,sizeof(a)/sizeof(a[0]));
   return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

6、归并排序
归并操作的工作原理如下：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

//将有序的X[s..u]和X[u+1..v]归并为有序的Z[s..v]   
void merge(int X[],int Z[],int s,int u,int v)
{
    int i, j, q;
	i = s;
	j = u + 1;
	q = s;
	while (i <= u && j <= v)
	{
		if (X[i] <= X[j])
		{
			Z[q++] = X[i++];
		}
		else
		{
		    Z[q++] = X[j++];
		}
	}
    while (i <= u)    //将X中剩余元素X[i..u]复制到Z   

    {
		Z[q++] = X[i++];
    }
	while (j <= v)     //将X中剩余元素X[j..v]复制到Z   

	{
		Z[q++] = X[j++];
	}
}

void mergePass(int X[], int Y[], int n, int t)  
{  
    int i = 0, j;  
    while( n - i >= 2 * t )     //将相邻的两个长度为t的各自有序的子序列合并成一个长度为2t的子序列   
    {  
       merge(X, Y, i, i + t - 1, i + 2 * t - 1);  
        i = i + 2 * t;  
    }  
  
    if( n - i > t )       //若最后剩下的元素个数大于一个子序列的长度t时   
        merge(X, Y, i, i + t - 1, n - 1);  
    else             //n-i <= t时，相当于只是把X[i..n-1]序列中的数据赋值给Y[i..n-1]   
        for( j = i ; j < n ; ++j )  
            Y[j] = X[j];  
}  
 
void mergeSort(int X[], int n)  
{  
    int t = 1;  
    int *Y = (int *)malloc(sizeof(int) * n);  
   while( t < n )  
    {  
       mergePass(X, Y, n, t);  
        t *= 2;  
       mergePass(Y, X, n, t);  
        t *= 2;  
   }  
    free(Y);  
}  
  
void print_array(int array[], int n)  
{  
    int i;  
    for( i = 0 ; i < n ; ++i )  
        printf("%d ", array[i]);  
    printf("\n");  
}  
 
int main()  
{  
    int array[] = {65, 2, 6, 1, 90, 78, 105, 67, 35, 23, 3, 88, -22};  
    int size = sizeof(array) / sizeof(int);  
    mergeSort(array, size);  
    print_array(array, size);  
    return 0;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76