算法名称 | 复杂度 | 实现关键 |
冒泡排序 | O(n^2) | (无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。 |
选择排序 | O(n^2) | (有序区,无序区)。在无序区里选择一个最小的元素跟在有序区的后面。 |
插入排序 | O(n^2) | (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。 |
希尔排序 | nlog^2(n) | 每一轮按照事先决定的间隔进行插入排序,间隔会依次缩小,最后一次一定要是1(插入)。 |
快速排序 | nlog(n) | (小数,枢纽元,大数)。 |
堆排序 | nlog(n) | |
桶排序 | O(n) | 将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。 |
1// 冒泡排序
2void bubble_sort(int a[], int n)
3{
4 int i = 0;
5 int j = 0;
6 for (i=0; i<n-1; i++)
7 {
8 // 比较相邻元素,若a[j]比a[j+1]大,则交换
9 // a[j]就像一个气泡一样“浮”到合适位置了
10 for(j=0; j<n-1-i; j++)
11 {
12 if(a[j]>a[j+1])
13 {
14 swap(&a[j], &a[j+1]);
15 }
16 }
17 }
18}
1// 选择排序
2void select_sort(int a[], int n)
3{
4 int i=0,j=0,min=0;
5 for (i=0; i < n-1; i++)
6 {
7 min = i;
8 // 找到最小值
9 for (j=i+1; j <= n-1; j++)
10 {
11 if (a[min] > a[j])
12 min = j;
13 }
14 if(min != i)
15 {
16 swap(&a[min], &a);
17 }
18 }
19}
1// 插入排序
2void insert_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 for (i = 1; i < n; i++)
8 {
9 // 取牌
10 tmp = a;
11 // 往前插的起始位置
12 j = i - 1;
13
14 // 大的a[j]都放后面,寻找出j
15 while ((j >= 0) && a[j] > tmp)
16 {
17 // 往后放一个
18 a[j+1] = a[j];
19 j--;
20 }
21
22 // 放到该放的位置
23 a[j+1]=tmp;
24 }
25}
1// 插入排序,选中的牌冒泡向前插入
2void insert_sort_2(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 //通过i选牌
7 for (i=1; i < n; i++)
8 {
9 // 冒泡向前插入(i-1 --> 0)
10 for (j=i-1; j>=0 && a[j] > a[j + 1]; j--)
11 {
12 swap(&a[j], &a[j+1]);
13 }
14 }
15 print_a(a, n);
16}
17`
[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
113 14 94 33 82
225 59 94 65 23
345 27 73 25 39
410
110 14 73 25 23
213 27 94 33 39
325 59 94 65 82
445
1// 希尔排序
2void shell_sort(int a[], int n)
3{
4 int i=0;
5 int j=0;
6 int tmp=0;
7 int gap=0;
8 while (gap <= n)
9 {
10 gap = gap*3 + 1;
11 }
12 while (gap > 0)
13 {
14 // 取牌
15 for (i = gap; i < n; i++)
16 {
17 // 冒泡向前插入(i-gap : gap : 0), 保证每列ok
18 for (j = i - gap; (j >= 0) && (a[j] > a[j + gap]); j = j - gap)
19 {
20 swap(&a[j], &a[j+gap]);
21 }
22 }
23 gap = (gap-1) / 3;
24 }
25}
1// 快速排序分区
2static int partition(int a[], int p, int r)
3{
4 int x=0;
5 int i=0;
6 int j=0;
7 // x为基准
8 x = a[r];
9 // i为界限,发现小于x的,就i++,再放到i处
10 i = p-1;
11 for (j=p; j<= r-1; j++)
12 {
13 if (a[j]<=x)
14 {
15 i++;
16 swap(&a, &a[j]);
17 }
18 }
19 // 至此,所有小于x的都到i左边了(a[0]~a[i-1]),a[r]是x,因此交换a[i+1]和a[r]
20 swap(&a[i+1], &a[r]);
21 return i+1;
22}
23
24// 快速排序
25void quick_sort(int a[], int p, int r)
26{
27 int q=0;
28 if (p < r)
29 {
30 // 在数据集之中,选择一个元素作为"基准"(pivot)
31 // 所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边
32 q = partition(a, p, r);
33 // 对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
34 quick_sort(a, p, q-1);
35 quick_sort(a, q+1, r);
36 }
37}
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |