排序算法

升序：从小到大
降序：从大到小

冒泡排序

原理：比较相邻两个数值，如果左边比右边大，则交换两个数值，直到最后两个，则最后一个就是最大值。
这个过程像冒泡，大的数值一直浮到顶部。

具体实现方法：
第一轮：先比较第一个数和第二个数，将小数放前，大数放后，然后比较第二个数和第三个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。到第一轮结束的时候，已经成功地将最大的数放到了最后。

第二轮：可能由于第二个数和第三个数的交换，使第一个数不再小于第二个数，所以新一轮的比较仍从第一对数开始比较，将小数放前，大数放后，一直比较到倒数第二个数，由于最后一个位置上的数已经是最大的，所以无须再对其进行比较。到第二轮结束的时候，在倒数第二个位置上得到一个新的最大数，也就是给定数据中的第二大的数。

重复以上过程，直到最后一轮比较完第一个数和第二个数，完成整个排序功能。

#include

void bubble(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++)
		{
			int temp=0;
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
}

int main()
{
	int arr[]={3,5,1,7,2};
	bubble(arr,5);
	for(int i=0;i<5;i++)
	{
		printf("%d\t",arr[i]);
	}
	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

1	2	3	5	7
1

选择排序

选择排序的原理是：选出数组中最小的数放在索引0，再选出第二小的数放在索引1，直到倒数第二个。
选择排序的意思也是，每次选最小的。

具体实现方法：
当前索引是0，那么从索引1开始比较，如果比索引0数值小，就交换，直到最后一个元素。

#include

void select(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=i+1;j<n-1;j++)
		{
			if(a[i]<a[j])
			{
				int temp=0;
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
}

int main()
{
	int a[]={4,6,2,8,1};
	select(a,5);
	for(int i=0;i<5;i++)
	{
		printf("%d\t",a[i]);
	}

		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

快速排序

快速排序的原理是：
每次选一个base，比base小的放base左边，比base大的放右边，然后递归处理base左右的两个数组。

具体实现方法是：

1.选择一个base，建立游标 i 和 j
2.从右向左滑动，当右边数值小于base值时停止；
3.从左向右滑动，当左边数值大于base值时停止；
4.交换a[i]和a[j]的值；
5.当i == j时退出；
6.交换base和a[i]的值；
7.递归操作

#include

void quicksort(int a[],int left,int right)
{
	if(left>=right) return ;
	int base=a[left]; //选择base值
	int i=left;
	int j=right;
	int temp=0;
	while(i<j)
	{
		while(i<j && a[j]>base) j--; //先进行右边搜索
		while(i<j && a[i]<base) i++; //再进行左边搜索
	   if(i<j)
	   {
	   		temp=a[i];//交换a[i]和a[j]的值
			a[i]=a[j];
			a[j]=temp;
	   }
	}

	temp=base;//交换base和a[i]的值
	base=a[i];
	a[i]=temp;
	quicksort(a,left,j-1);
	quicksort(a,j+1,right);
}


int main()
{
	int arr[]={4,2,6,1,3};
	quicksort(arr,0,4);
	for(int i=0;i<5;i++)
	{
		printf("%d\t",arr[i]);
	}
	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

1	2	3	4	6
1

归并排序

归并排序的原理是：

1.核心原理是对两个有序数组进行合并，比如：{1,4,6,8}，{2,7,9,12}；合并成{1,2,4,6,7,8,9,12}；
2.合并的首要目标是分解，将数组分解至单个元素，就是有序数组了！注意分解的时间是O(1)时间；
3.分解完所有数组就要进行归并了，利用条目1的归并函数，对所有有序数组俩俩合并，合成一个有序数组，直至最后，就构成了一个有序数组。

#include
#include
//对数组的局部空间进行排序
void merge(int a[],int left,int right)
{
	int mid=(left+right)/2;
	int i=left;
	int j=mid+1;
	int k=left; //out的索引
	int *tmp=(int *)malloc(sizeof(int)*(right-left+1)); //建立临时数组，用于存储排序好的数组


	//归并，直到一个数组到达边界
	while( i<=mid && j<=right)
	{
		if (a[i]<a[j]) tmp[k++]=a[i++];
		else tmp[k++]=a[j++];
	}

	//处理剩余元素的数组，原样放入out中
	while(i<=mid) tmp[k++]=a[i++];
	while(j<=right) tmp[k++]=a[j++];

	//将排序好的临时数组放回源数组中
	for(int m=left;m<right+1;m++)
	{
		a[m]=tmp[m];
	}
	free(tmp);
	return;
}

//递归分区，因为要划分区间，所以递归条件是数组区间，因此参数是数组及左右区间。
void merge_sort(int a[],int left,int right)
{
	if(left>=right) return;
	//防止数据溢出
	int mid=(left+right)/2;

	merge_sort(a,left,mid);
	merge_sort(a,mid+1,right);

	merge(a,left,right);

	return ;
}



int main()
{
	int arr[]={6,1,5,3,4,7,2,9,8};
//	merge(arr,0,8);
	merge_sort(arr,0,8);
	for(int i=0;i<9;i++)
	{
		printf("%d\t",arr[i]);
	}
	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

1	2	3	4	5	6	7	8	9
1

查找算法

二分查找

二分查找的思路是：
每次取中间值，排除一半数据；直到找到和目标相等的值。

实现方法：

1.前提是有序数组；
2.每次取中间值，进行比较，选择符合的一半数组；
3.递归查找

#include

bool binSearch(int a[],int n,int tar)
{
	int left=0;
	int right=n-1;

	while(left<=right)
	{
		int mid=left+(right-left)/2;
		if(a[mid]>tar) right=mid-1;
		else if(a[mid]<tar) left=mid+1;
		else return true;
	}

	return false;
}

int main()
{
	int arr[]={1,3,5,7,9};
	bool x=binSearch(arr,5,3);
	if(x)printf("TRUE\n");
	else printf("FALSE\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

TRUE
1