ddddfang's Blog.

sort-related

排序 第k小的数
字数统计: 869阅读时长: 4 min
2019/01/30 Share

快速排序中的核心函数

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
int Partition(int a[], int start, int end) //返回调整后基准数的位置(也就是它在最终排序数组中的位置)
{
    int i = start, j = end;
    int x = a[i]; //a[i]就是第一个坑，这里可以先安排一个a[i] <---> a[randint(start,end)]
    while (i < j)
    {
        // 坑在左边，那就先从右向左找小于x的数来填a[i]
        while(i < j && a[j] >= x)
            j--;
        if(i < j)    // i < j 尚满足说明还没有到尽头
        {
            a[i] = a[j]; //将a[j]填到a[i]中，a[j]就形成了一个新的坑
            i++;
        }
        // 从左向右找大于或等于x的数来填a[j]
        while(i < j && a[i] < x)
            i++;
        if(i < j)
        {
            a[j] = a[i]; //将a[i]填到a[j]中，a[i]就形成了一个新的坑
            j--;
        }
    }
    //退出时，i等于j。将x填到这个坑中。
    a[i] = x;
    return i;
}

img

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//还能优化，如start 与 end区间够小的时候改用插入排序
void _qsort(int *a, int start, int end)
{
    if(start >= end)
    {
        return;
    }
    int i = Partition(a,start,end);
    _qsort(a, start, i-1);
    _qsort(a, i+1, end);
}
void Qsort(int *a, int len)
{
    if(a == NULL || len <= 0)
        return;
    int start = 0;
    int end = len -1;
    _qsort(a, start, end);
}

快速排序对于在内存中的数据排序很有效，但如果数据位于磁盘且数据量巨大，则归并排序可能更适合。因为可以使用多个线程（通道）进行固定大小的排序，最后将排序结果归并即可，这些操作仍是需要进行专门设计的

实际使用快速排序不是使用我们的轮子^v^, eg. vs下使用快速排序(.c)：

1
2
3
4
5
6
7
8
9
10
11
#include <stdlib.h>
#include <algorithm>

#define SIZE 100
int gArray[SIZE] = {……};

int cmp(const void * a, const void *b)
{
    return (*(int *)a - *(int *)b);    //a>b 返回正，则递增排序
}
qsort(gArray, SIZE, cmp);

利用快排核心函数找第k小的数(<剑指offer p167>)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//（ 据说复杂度为 O(n) ）
int getKth(int *a, int len, int k)
{
    if(a == NULL || len <= 0)
        return;
    int s = 0;
    int e = len -1;
    int i=Partition(a,s,e)；
    while(i != k-1)
    {
        if(i>k-1)
        {
            e = i-1;
            i = Partition(a,s,e);
        }
        if(i<k-1)
        {
            s = i+1;
            i = Partition(a,s,e);
        }
    }
    return a[i];    //或a[k-1], 其左均比其小, 其右均比其大
}

插入排序

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
int insertSort(int *a ,int len)
{
    int i;
    for(i = 1;i <len; i++)
    {
        for(j = i; j>0 && a[j]<a[j-1]; j--)
        {
            a[j] <-> a[j-1];
        }
    }
}

int insertSortBetter(int *a ,int len)
{
    int i;
    for(i = 1;i <len; i++)
    {
        t = a[i];
        for(j = i; j>0 && a[j]<a[j-1]; j--)
        {
            a[j] = a[j-1];
        }
        a[j] = t;
    }
}

归并排序

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
void mergeSort(int *a, int s, int e) //将a数组的[s,e]区间排序完成
{
    if(s < e)
    {
        int mid = (s+e)/2;
        mergeSort(a,s,mid);
        mergeSort(a,mid+1,e);
        merge(a,s,mid,e);  //将两个排好序的半个归并到一起
    }
}
void merge(int *a, int start, int mid, int end) //将 [start,mid] 与 [mid+1,end] 归并
{
    int i, j=0;
    int s1 = start, e1 = mid, s2 = mid+1, e2 = end;
    int *tmp = (int *)malloc((end-start+1)*sizeof(int));

    while(s1<= e1 && s2 <= e2)
    {
        if(a[s1] < a[s2])
            tmp[j++] = a[s1++];
        else
            tmp[j++] = a[s1++];
    }
    //处理可能的残余
    while(s1 <= e1)
        tmp[j++] = a[s1++];
    while(s2 <= e2)
        tmp[j++] = a[s2++];
    for(i = 0; i<end-start+1;i++)
        a[start+i] = tmp[i];
    free(tmp);
}

原文作者：ddddfang

原文链接：https://ddddfang.github.io/2019/01/30/sort-related/

发表日期：January 30th 2019, 3:55:05 pm

更新日期：January 30th 2019, 4:19:36 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 快速排序中的核心函数
  2. 2. 快速排序
  3. 3. 利用快排核心函数找第k小的数(<剑指offer p167>)
  4. 4. 插入排序
  5. 5. 归并排序
Total : 42
2019
binary-search bitmap caffe c++ 单例模式 common misc makefile 宏 顺序容器 智能指针 排序 shell linux command docker blog ffmpeg gdb gitbook p4 printf 可变参数 static and dynamic library 第k小的数 ubuntu setup 并查集 git draw.io markdown vscode office2016 密钥 键值对集合 链表 最大堆(大顶堆) swig python c vim 红黑树 skip-list hash-table
algorithm-and-data-struct caffe common-misc cpp linux-daily ffmpeg