面试题

排序算法总结(多图)

2019-03-24  本文已影响234人  凯睿看世界

1. 概述

算法名称 复杂度 实现关键
冒泡排序 O(n^2) (无序区,有序区)。从无序区通过交换找出最大元素放到有序区前端。
选择排序 O(n^2) (有序区,无序区)。在无序区里选择一个最小的元素跟在有序区的后面。
插入排序 O(n^2) (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。
希尔排序 nlog^2(n) 每一轮按照事先决定的间隔进行插入排序,间隔会依次缩小,最后一次一定要是1(插入)。
快速排序 nlog(n) (小数,枢纽元,大数)。
堆排序 nlog(n)
桶排序 O(n) 将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。

不稳定的排序:
稳定性一个形象的比喻,本来有两个并列第三,一排序把原来并列的顺序给变了。
比如:选择排序、快速排序、堆排序、希尔排序;
参考链接

2. 冒泡排序

image

每次都把未排序的第一个作为起始点,然后逐渐冒泡上升,之后未排序区越来越少,最终排序完成

image
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}

3. 选择排序

image

每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

image
 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[i]);
17        }
18    }
19}

4. 插入排序

image

每次排序从未排序区取一个“牌”,然后往前插入(包括了两步:大的往后移,把牌放到合适位置)。

image
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[i];
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`

5. 希尔排序

对插入排序再加一个步长的循环就是希尔排序了,例如

1[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]

按照5步长排序,则相当于按列先进行排序(实际是通过下标实现的)

113 14 94 33 82225 59 94 65 23345 27 73 25 39410

排序后结果为

110 14 73 25 23213 27 94 33 39325 59 94 65 82445

多次循环后,只需要最终步长为1即可。

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}

6. 快速排序

image

每次迭代都选出一个基准,左边放小的,右边放大的,最终迭代完成。

image
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[i], &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}

原文

上一篇下一篇

猜你喜欢

热点阅读