六大算法
一、冒泡排序(BubbleSort)基本思想过程平均时间复杂度C代码实现优化
二、二分查找（Binary Search）算法要求时间复杂度查找过程C代码示例
三、快速排序(Quicksort)基本思想示例平均时间复杂度C代码实现
四、希尔排序(Shell Sort)基本思想过程平均时间复杂度C代码实现
五、选择排序(SelctionSort)基本思想过程平均时间复杂度C代码实现
六、插入排序(Insertion Sort)基本思想过程平均时间复杂度C代码实现
一、冒泡排序(BubbleSort)
基本思想
两个数比较大小，较大的数下沉，较小的数冒起来。
过程
比较相邻的两个数据，如果第二个数小，就交换位置。从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。继续重复上述过程，依次将第2.3…n-1个最小数排好位置。
平均时间复杂度
O(n2)
C代码实现
int arr
[] = {34, 27, 55, 8, 97};
int length
= sizeof(arr
)/sizeof(arr
[0]);
void bubbleSort(int arr
[], int length
)
{
int temp
;
for (int i
= 0; i
< length
- 1; i
++) {
for (int j
= length
- 1; j
> i
; j
--) {
if (arr
[i
] > arr
[j
]) {
temp
= arr
[j
];
arr
[j
] = arr
[i
];
arr
[i
] = temp
;
}
}
}
}
优化
针对问题 数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。
方案 设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。
void bubbleSort(int arr
[], int length
)
{
int temp
;
Boolean flag
;
for (int i
= 0; i
< length
- 1; i
++) {
flag
= false;
for (int j
= length
- 1; j
> i
; j
--) {
if (arr
[i
] > arr
[j
]) {
temp
= arr
[j
];
arr
[j
] = arr
[i
];
arr
[i
] = temp
;
flag
= true;
}
}
if (flag
== false)
break;
}
}
二、二分查找（Binary Search）
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
算法要求
必须采用顺序存储结构。必须按关键字大小有序排列。
时间复杂度
O(log2n）
查找过程
首先，假设表中元素是按升序排列， 将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功； 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
C代码示例
int arr1
[] = {1, 2, 7, 8, 9};
int target
= BinarySearch(arr1
, 0, length
- 1, 8);
int
BinarySearch(int arr
[], int low
, int high
, int target
)
{
while(low
<= high
)
{
int mid
= (low
+ high
)/2;
if(arr
[mid
] > target
)
high
= mid
- 1;
else if(arr
[mid
] < target
)
low
= mid
+ 1;
else
return mid
;
}
return -1;
}
三、快速排序(Quicksort)
基本思想
先从数列中取出一个数作为key值；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复第二步，直至各区间只有1个数。
示例
假设用户输入了如下数组：
下标012345
数据627389
创建变量i=0（指向第一个数据）, j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。 我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：
下标012345
数据327689
i=0 j=3 k=6
接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：
下标012345
数据326789
i=2 j=3 k=6
称上面两次比较为一个循环。 接着，再递减变量j，不断重复进行上面的循环比较。 在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：
下标012345
数据326789
如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。 然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。 注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
平均时间复杂度
O(N*logN)
C代码实现
int arr
[] = {34, 27, 55, 8, 97};
int length
= sizeof(arr
)/sizeof(*arr
);
quickSort(arr
, 0, length
-1);
void quickSort(int
*a
, int left
, int right
)
{
if(left
>= right
)
{
return ;
}
int i
= left
;
int j
= right
;
int key
= a
[left
];
while(i
< j
) {
while(i
< j
&& key
<= a
[j
]) {
j
--;
}
a
[i
] = a
[j
];
while(i
< j
&& key
>= a
[i
]) {
i
++;
}
a
[j
] = a
[i
];
}
a
[i
] = key
;
quickSort(a
, left
, i
- 1);
quickSort(a
, i
+ 1, right
);
}
四、希尔排序(Shell Sort)
基本思想
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
过程
平均时间复杂度
O(n1.5)
C代码实现
int arr
[] = {34, 27, 55, 8, 97};
int length
= sizeof(arr
)/sizeof(arr
[0]);
void shellSort(int arr
[], int length
)
void shellSort(int arr
[], int length
)
{
int temp
= 0;
int incre
= length
;
while(true){
incre
= incre
/2;
for(int k
= 0;k
<incre
;k
++){
for(int i
=k
+incre
;i
<length
;i
+=incre
){
for(int j
=i
;j
>k
;j
-=incre
){
if(arr
[j
]<arr
[j
-incre
]){
temp
= arr
[j
-incre
];
arr
[j
-incre
] = arr
[j
];
arr
[j
] = temp
;
}else{
break;
}
}
}
}
if(incre
== 1){
break;
}
}
}
五、选择排序(SelctionSort)
基本思想
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换； 第二次遍历n-2个数，找到最小的数值与第二个元素交换； 。。。 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
过程
平均时间复杂度
O(n2)
C代码实现
int arr
[] = {34, 27, 55, 8, 97};
int length
= sizeof(arr
)/sizeof(*arr
);
selectSort(arr
, length
);
void selectSort(int arr
[], int length
)
{
for (int i
= 0; i
< length
- 1; i
++) {
int minIndex
= i
;
for (int j
= i
+ 1; j
< length
; j
++) {
if (arr
[minIndex
] > arr
[j
]) {
minIndex
= j
;
}
}
if (minIndex
!= i
) {
int temp
= arr
[i
];
arr
[i
] = arr
[minIndex
];
arr
[minIndex
] = temp
;
}
}
}
六、插入排序(Insertion Sort)
基本思想
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
过程
平均时间复杂度
O(n2)
C代码实现
int arr
[] = {34, 27, 55, 8, 97};
int length
= sizeof(arr
)/sizeof(*arr
);
insertSort(arr
, length
);
void insertSort(int arr
[], int length
)
{
for (int i
= 0; i
< length
- 1; i
++) {
for (int j
= i
+ 1; j
> 0; j
--) {
if (arr
[j
] < arr
[j
- 1]) {
int temp
= arr
[j
- 1];
arr
[j
- 1] = arr
[j
];
arr
[j
] = temp
;
} else {
break;
}
}
}
}
