数据结构复习--排序

@(笔试面试)

数据结构复习 — 排序算法

排序算法是在笔试面试中常考，以前在写复习材料的时候，也整理过，但是具体的算法并没有完全测试过，前些天在查找桶排序的算法时，发现别人已经整理的很好了，我拿过来练练手，并记录下来。

插入排序

直接插入排序

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertsort(int nums[],int n)
{
    // original insert sort
    int i,j;
    int key;
    for(i = 1;i<n;++i)
    {
        key = nums[i];
        for(j=i-1;j>=0 && key < nums[j];--j)
            nums[j+1] = nums[j];
        nums[j+1] = key;
    }
}

稍作改进，在每次插入的时候，首先检查与已排序元素的最后一个元素比较，若比最后一个元素大，则不用插入排序；否则进行插入排序，性能没有改进多少，就是程序结构清晰了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void insertsort2(int nums[],int n)
{
    // advance insert sort
    int i,j;
    int key;
    for(i =1;i<n;++i)
    {
        key = nums[i];
        if(key < nums[i-1])
        {
            for(j=i-1;j>=0 && key < nums[j];--j)
                nums[j+1] = nums[j];
            nums[j+1] = key;
        }
    }
}

再改进一点，就是二分插入排序，针对前半部分进行二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void binaryinsertsort(int nums[],int n)
{
    // binary insert sort
    int i,j,low,high,mid;
    int key;
    for(int i=1;i<n;++i)
    {
        key = nums[i];
        low = 0;high = i-1;
        while(low <= high)
        {
            mid = (low+high)/2;
            if(nums[mid] > key)
                high = mid-1;
            else
                low = mid +1;
        }
        for(j =i-1;j>high;--j)
            nums[j+1] = nums[j];
        nums[j+1] = key;
    }
}

交换类排序

冒泡排序

每次都要交换：

1
2
3
4
5
6
7
8
9
10
11
12
void bubblesort(int nums[],int n)
{
    // original bubble sort
    for(int i=0;i<n;i++)
    {
        for(int j = 1;j<n-i;++j)
        {
            if(nums[j] < nums[j-1])
                swap(nums[j],nums[j-1]);
        }
    }
}

稍微改进一下，若一次冒泡的过程中没有发生一次交换，那就正好有序了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void bubblesort(int nums[],int n)
{
    // original bubble sort
    bool flag = false;
    for(int i=0;i<n;i++)
    {
        flag = false;
        for(int j = 1;j<n-i;++j)
        {
            if(nums[j] < nums[j-1])
            {
                swap(nums[j],nums[j-1]);
                flag = true;
            }
        }
        if(!flag)
            break;
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int partition(int nums[],int low,int high)
{
    int key = nums[low];
    while(low < high)
    {
        while(low < high && key <= nums[high]) -- high;
        nums[low] = nums[high];
        while(low < high && key >= nums[low]) ++low;
        nums[high] = nums[low];
    }
    nums[low] = key;
    return low;
}

void QuickSort(int nums[],int low,int high)
{
    // quick sort
    if(low < high)
    {
        int pivotloc = partition(nums,low,high);
        QuickSort(nums,low,pivotloc-1);;
        QuickSort(nums,pivotloc+1,high);
    }
}

选择类排序

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectsort(int nums[],int n)
{
    // simple select sort
    int minidx;
    for(int i=0;i<n;i++)
    {
        minidx = i;
        for(int j=i;j<n;++j)
        {
            if(nums[minidx] > nums[j])
                minidx = j;
        }
        if(minidx != i)
            swap(nums[minidx],nums[i]);
    }
}

递归版的简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
void simplleSelectSortMore(int nums[],int n)
{
    if(nums == NULL || n <= 0)
        return;
    int idx = 0;
    for(int i=0;i<n;++i)
        if(nums[idx] > nums[i])
            idx = i;
    if(idx != 0)
        swap(nums[0],nums[idx]);
        simplleSelectSortMore(nums+1,n-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
26
27
28
29
30
31
32
33
34
void maxHeap(int nums[],int n,int i)
{
    int left,right,largest;
    left = (i+1)*2 - 1;
    right = (i+1)*2;
    largest  = left;
    if(left >= n)
        return;
    if(right < n && nums[largest] < nums[right])
        largest = right;
    if(nums[i] < nums[largest])
    {
        swap(nums[i],nums[largest]);
        maxHeap(nums,n,largest);
    }
}

void createHeadp(int nums[],int n)
{
    for(int i=n/2;i >=0;--i)
        maxHeap(nums,n,i);
}

void heapSort(int nums[],int n)
{
    if(nums == NULL || n <= 0)
        return;
    createHeadp(nums,n);
    for(int i=n-1;i>0;--i)
    {
        swap(nums[0],nums[i]);
        maxHeap(nums,i,0);
    }
}

参考的博客里面的下标都是从1开始，我写的程序都是从0开始的，但是并不影响理解程序。

归并排序

也是分治思想

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 merge(int nums[],int beg,int end,int mid)
{
    int *arr_l = new int[mid - beg + 1];
    int *arr_r = new int[end - mid];
    int i,j,k;
    for(i = 0;i<mid-beg+1;i++)
        arr_l[i] = nums[beg + i];
    for(i = 0;i<end-mid;++i)
        arr_r[i] = nums[mid + i + 1];
    i = 0;
    j = 0;
    for(k = beg;k<=end;++k)
    {
        if(arr_l[i] < arr_r[j])
            nums[k] = arr_l[i++];
        else
            nums[k] = arr_r[j++];
    }
    delete []arr_l;
    delete []arr_r;
}

void mergeSort(int nums[],int beg,int end)
{
    int mid = (beg + end) / 2;
    if(beg <end)
    {
        mergeSort(nums,beg,mid);
        mergeSort(nums,mid+1,end);
        merge(nums,beg,end,mid);
    }
}

线性时间排序算法

计数排序

基数排序

桶排序

参考

  1. CSDN经典排序总结
赏

还没想好

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

张小牙，曾就职于Thoughtworks，目前从事图像处理与深度学习相关的算法工作，擅长C++