1. 排序

插入排序

概述

  • 将新元素插入到有序序列中。

    步骤

  • 假设序列中第一个元素为有序序列，将其余元素都当做待插入元素处理
  • 每次当前待插入元素与有序序列最后一个元素开始依次进行比较，如果小于被比较元素，则进行交换，交换后继续进行比较直至有序序列第一个元素
  • 将列表分为有序区，待插入的无序区

代码实现

Python 插入排序
1
2
3
4
5
6
def sort_cr(v_list):
    for i in range(len(v_list)):
        for j in range(i,0,-1):
            if v_list[j] < v_list[j-1]:
                v_list[j],v_list[j-1] = v_list[j-1],v_list[j]
    return v_list
C 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void svoid insertion_sort(int array[],int first,int last)
{
    int i,j;
    int temp;
    for(i=first+1;i<last;i++)
    {
        temp=array[i];
        j=i-1;
        //与已排序的数逐一比较，大于temp时，该数移后
        while((j>=0)&&(array[j]>temp))
        {
            array[j+1]=array[j];
            j--;
        }
        //存在大于temp的数
        if(j!=i-1)
            array[j+1]=temp;
    }
}

性能分析

时间复杂度

时间复杂度为O(n^2)

算法稳定性
  • 比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
  • 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
  • 相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，排序是稳定的。

选择排序

概述

  • 走访列表长度次，每次选出最小（或最大）的元素，重新排顺序

步骤

  • 第一次选出最小（或最大）的元素，放在列表的起始位置，即与开头元素交换
  • 接下来每次选出最小（或最大）的元素，与索引等于当前的循环次数的元素进行交换
  • 将列表分为已选择出来的有序区，等待选择的无序区

代码实现

Python 选择排序
1
2
3
4
5
6
7
8
def sort_xz_1(v_list):
    for i in range(len(v_list)-1):
        min = i
        for j in range(i+1,len(v_list)):
            if v_list[min] > v_list[j]:
                min = j
        v_list[min],v_list[i] = v_list[i],v_list[min]
    return v_list
C选择排序
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
35
36
void swap(int*a,int*b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void select_sort(int A[],int n)
{
    register int i,j,min,m;
    for(i=0;i<n-1;i++)
    {
        min=i;//查找最小值
        for(j=i+1;j<n;j++)
        {
            if(A[min]>A[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            swap(&A[min],&A[i]);
            printf("第%d趟排序结果为:\n",i+1);
            for(m=0;m<n;m++)
            {
                if(m>0)
                {
                    printf("");
                }
                printf("%d",A[m]);
            }
            printf("\n");
        }
    }
}

性能分析

时间复杂度

比较时间复杂度为O(n^2)
交换时间复杂度未O(n)

算法稳定性
  • 在一趟选择中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
  • 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

冒泡排序

概述

  • 重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
  • 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

步骤

  • 走n-1次，两两相比，当次当前的比较元素的索引最大值为未被比较元素（未冒泡）的索引-1
  • 每次从第一个元素开始进行两两比较。如果当前元素比下一个元素大，就交换他们两个，接下来有下一个元素与自己的下一个元素进行两两比较。
  • 当次最后的元素是本轮比较结果中最大的数，已冒好泡，下次无需理会。
  • 重复对未冒泡好的左区进行冒泡处理
  • 每轮比较结束后 ，已冒泡元素新增一个

代码实现

Python 冒泡排序

1
2
3
4
5
6
def sort_mp_py(v_list):
    for i in range(len(v_list)-1):
        for j in range(len(v_list)-i-1):
            if v_list[j] > v_list[j+1]:
                v_list[j],v_list[j+1] = v_list[j+1],v_list[j]
    return v_list

C冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
void sort_mp_c (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) 
        for (j=0; j<len-1-i; j++) { 
            if (arr[j] > arr[j+1]) {  
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}

性能分析

时间复杂度

平均时间复杂度为O(n^2)

算法稳定性

  • 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
  • 如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
Copyright © 2020 Fzg5_Shelling | Powered by Hexo | Theme by Snippet | Deploys by Netlify