- 选择排序
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
3、将两个排序好的子序列合并成一个最终的排序序列,直到所有元素均排序完毕
4、选择排序是非常稳定的
5、无论什么数据进去时间复杂度都是 O(n2)
6、所以用到它的时候，数据规模越小越好
7、选择排序，实例代码如下.
#include <stdio.h>
#define LEN 10
int data[LEN] = {10, 1, 6, 3, 4, 8, 2, 9, 5, 0};
void print_data(void)
{
printf("%d %d %d %d %d %d %d %d %d %d\n",
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7],
data[8], data[9]);
}
int main(int argc, char *argv[])
{
int i, j, temp;
print_data();
for(i = 0; i < LEN-1; i++){
for(j = i+1; j < LEN; j++) {
if(data[i] > data[j]) {//找最小的数
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
print_data();
}
}
return 0;
}
- 冒泡排序
1、冒泡排序算法属于 非线性时间比较类排序 中的交换排序
2、比较相邻的元素。如果第一个比第二个大，就交换它们两个
3、把长度为n的输入序列分成两个长度为n/2的子序列
4、从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
5、时间复杂度(平均和最坏)都是: O(n*n)
6、时间复杂度(最好): O(n)
7、冒泡排序，实例代码如下.
#include <stdio.h>
#define LEN 10
int data[LEN] = {10, 1, 6, 3, 4, 8, 2, 9, 5, 0};
void print_data(void)
{
printf("%d %d %d %d %d %d %d %d %d %d\n",
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7],
data[8], data[9]);
}
int main(int argc, char *argv[])
{
print_data();
for(int i = 0; i < LEN; i++) {
for(int j = 0; j < LEN-i-1; j++) {
if(data[j] > data[j+1]) {
int temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
print_data();
}
}
}
return 0;
}
- 归并排序
1、归并排序算法采取分而治之 (Divide-and-Conquer)的策略.
$ 时间复杂度为: Θ(nlgn)
2、把长度为n的输入序列分成两个长度为n/2的子序列
3、对这两个子序列分别采用归并排序，这是一个递归的过程
4、将两个排序好的子序列合并成一个最终的排序序列
5、归并排序，实例代码如下.
#include <stdio.h>
#define LEN 10
int data[LEN] = {10, 1, 6, 3, 4, 8, 2, 9, 5, 0};
void print_data(const char *head, int start, int mid, int end)
{
printf("%s (%d-%d, %d-%d) %d %d %d %d %d %d %d %d %d %d\n",
head, start, mid, mid+1, end,
data[0], data[1], data[2], data[3],
data[4], data[5], data[6], data[7],
data[8], data[9]);
}
void merge(int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int left[n1], right[n2];
int i, j, k;
for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = data[start+i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = data[mid+1+j];
i = j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
data[k++] = left[i++];
else
data[k++] = right[j++];
while (i < n1) /* left[] is not exhausted */
data[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
data[k++] = right[j++];
}
void sort(int start, int end)
{
int mid;
if (start < end) {
mid = (start + end) / 2;
print_data("sort", start, mid, end);
sort(start, mid);
sort(mid+1, end);
merge(start, mid, end);
print_data("merge", start, mid, end);
}
}
int main(int argc, char *argv[])
{
sort(0, LEN-1);
return 0;
}
- 插入排序
1、插入排序算法采取增量式(Incremental)的策略解决问题，
每添加一个元素到已排序的子序列中，会逐步将整个数组排序完.
$ 所以插入排序的时间复杂度为: O(n*n)
2、正向插入排序，实例代码如下.
#include <stdio.h>
#define LEN 10
int data[LEN] = {10, 1, 6, 3, 4, 8, 2, 9, 5, 0};
extern void print_data(void);
int main(int argc, char *argv[])
{
int i, j, temp;
for(j = 1; j < LEN; j++) { //LEN-1
print_data();
temp = data[j]; //a1
i = j - 1; //a2
while(i >= 0 && data[i] > temp){//m
data[i+1] = data[i];//a3
i--; //a4
}
data[i+1] = temp; //a5
}
print_data();
return 0;
}
void print_data(void)
{
for(int i = 0; i < LEN; i++)
printf("%d ", data[i]);
printf("\n");
}
3、解决同一个问题可以有很多种算法，比较算法的好坏主要标准就是时间复杂度.
1)实例中计算复杂度时忽略print_data和printf输出语句
2)最外层的for循环执行了 LEN-1 次，内层while循环假设执行m次，
主要取决于原始数据，这里将括号内的比较和赋值的时间忽略了，
总的执行时间粗略估计: (LEN-1)(a1+a2+a5+m(a3+a4))
3)最好的情况下(即数据已正向排好)执行时间为:
(a1+a2+a5)(LEN-1) = (a1+a2+a5)LEN - (a1+a2+a5)
表示成: a*LEN - b，是LEN的线性函数
4)最坏的情况下(数据逆向排好)执行时间为:
(LEN-1)(a1+a2) + (a3+a4)(LEN*(LEN-1)/2)
5)最坏和随机平均情况下都可以表示成:
a*LEN*LEN + b*LEN + c 是LEN的二次函数
6)分析算法时间复杂度时，主要关心最坏情况，该算法当LEN愈来愈大时，
常数时间可以忽略不计，所以该插入排序算法的时间复杂度为:
O(LEN*LEN) O表示小于等于