内容提要

1. 我掌握的排序算法的时间复杂度

2. 我掌握的6种排序算法(插入, 冒泡, 选择, 归并, 快速, 希尔)

3. 迷宫的搜索方法(深度优先 + 广度优先)

 

---

各种排序的时间复杂度

名称	稳定 否	平均时间复杂度
插入排序	稳定	n2
冒泡排序	稳定	n2
选择排序	否	n2
归并排序	稳定	nlog2n
希尔排序	否	n2
快速排序	否	nlog2n

 

---

各种排序算法

1. 插入排序

类似打扑克, 来一个数, 从这个数的前一个数开始, 一直到第一个数, 比这个数小的, 比如位置是 a, 那么 a 之前的都比这个数小, 所以, 要移动 a 以后到这个数以前的数, 向后移动一位, 然后将这个数插入到 a+1 的位置上

#include<stdio.h>

int a[10] = {

    10, 2, 5, 1, 3, 4, 6, 7, 9, 8

};

void insert_sort()

{

    int j = 1;     /* 插入location */

    int i ;

    int key = -1;

    for (j=1; j<10; j++) {

        i = j - 1;

        key = a[j];

        /* 移动元素 */

        while (i>=0 & a[i] > key) {

            a[i+1] = a[i];

            i--;

        }

        a[i+1] = key;

    }

}

int main(void)

{

    int i = 0;

    printf("-------- now the data --------:\n");

    for (i=0; i<10; i++) {

        printf("%d, ", a[i]);

    }

    insert_sort();

    printf("\n-------- after insert sort --------:\n");

    for (i=0; i<10; i++) {

        printf("%d, ", a[i]);

    }

}

 

2. 冒泡排序

第一个循环就是控制循环次数, 没有别的意义, 在每次循环内部, 两两比较, 这样, 最大的数, 第一次循环就冒出去了, 以此类推, 逐渐冒出去第2大, 第3大的数.

#include <stdio.h>

#define LEN 10

int a[LEN] = {10, 5, 6, 7, 8, 1, 4, 2, 9, 3};

void maopao_sort(void)

{

    int count = 0;

    int circle = LEN;

    int i = 0;

    int j = 1;

    int temp;

    for (count=0; count<LEN; count++) {    // 总循环次数 

        circle--;

        for (i=0; i<circle; i++) {

            if (a[i+1] < a[i]) {

                temp = a[i+1];

                a[i+1] = a[i];

                a[i] = temp;

            }

        }

    }   

}

int main(void)

{

    int i = 0;

    maopao_sort();

    for (i=0; i<LEN; i++) {

        printf("%d,", a[i]);

    }

    return 0;

}

 

3. 选择排序

第一个循环是控制循环次数, 每次找出这个循环中最小的数,放在第一个位置, 然后再从第2个数开始找, 找出第二次循环中最小的数,放在第2个的位置上, 以此类推

#include<stdio.h>

#define LEN 10

int a[LEN] = {

    10, 2, 5, 3, 4, 1, 7, 6, 8, 9

};

void selectSort()

{

    int temp;

    int i;

    int j;

    for (i=0; i<LEN; i++) {

        for (j=i+1; j<LEN; j++) {

            if (a[j] < a[i]) {

                temp = a[i];

                a[i] = a[j];

                a[j] = temp;

            }

        }

    }

}

int main(void)

{

    int i;

    selectSort();

    for (i=0; i<LEN; i++) {

        printf("%d,", a[i]);

    }   

    return 0;

}

 

4. 归并排序(个人最喜欢的排序)

递归思想, 首先, 将所有的数分为两部分, 这两部分排好序后,再整合(归并) merge, 整合时, 因为左右两边都是已经排好序的, 所以, 排序起来容易很多.

#include<stdio.h>

#define LEN 10

int a[LEN] = {

    10, 7, 4, 2, 3, 1, 8, 9, 5, 6

};

void merge(int start, int mid, int end)

{

    int n1 = mid - start + 1;

    int n2 = end - mid;

    int left[n1];

    int right[n2];

    int i, j, k;

    // init left and right

    for (i=0; i<n1; i++) {

        left[i] = a[start+i];

    }   

    for (j=0; j<n2; j++) {

        right[j] = a[mid+1+j];

    }

    i = j = 0;

    k = start;

    // merge

    while (i < n1 && j < n2) {

        if (left[i] <= right[j]) {

            a[k++] = left[i++];

        } else {

            a[k++] = right[j++];

        }

    }

    while (i < n1) {

        a[k++] = left[i++];

    }

    while (j < n2) {

        a[k++] = right[j++];

    }

           

}

void sort(int start, int end)

{

    int mid;

    if (start < end) {

        mid = (end + start) / 2;

        sort(start, mid);

        sort(mid+1, end);

        merge(start, mid, end);

    }   

}

 

int main(void)

{

    int i;

    sort(0, LEN-1);

    for(i=0; i<LEN; i++) {

        printf("%d,", a[i]);

    }   

   

    return 0;

}

5. 希尔排序

插入排序的升级版, 算法: 首先定义一个步长, 一般设定为 LEN/2, 然后相隔这个步长的元素进行插入排序, 这个步长逐步缩小, 直到步长为1 .

#include<stdio.h>

# define LEN 10

int a[LEN] = {

    10, 2, 4, 1, 6, 8, 3, 5, 9, 7

} ;

void Shell_sort()

{

    int d = LEN / 2;

    int j;

    int i;

    int temp;

    while (d > 0) {    /* 步长控制总的循环次数 */

        for (j=d; j<LEN; j++) {  /* 类似插入排序中的 j=1 */

            i = j-d;             /* 从插入为的前一位开始比较, 注意这个前一位是间隔前步长位 */

            temp = a[j];

            /* 移位 */

            while (i>=0 && a[i] > temp) {   /* 注意: 这里一定要是 temp, 而不能是 a[j], 因为循环内部已经改变了a[j]的值 */

                a[i+d] = a[i];

                i -= d;

            }

            a[i+d] = temp;     /* 插入操作 */ 

        }

       

        d = d/2;   

    }

}

int main(void)

{

    int i;

    Shell_sort();   

    for (i=0; i<10; i++) {

        printf("%d, ", a[i]);

    }

}

 

6. 快速排序

快速排序是冒泡排序的升级版, 采用了分治策略, 首先把序列分成两个子序列, 递归对子序列进行排序. 首先找到一个轴, 对序列进行重新排序, 比轴小的放到轴左边, 比轴的放到轴右边, 划分后, 轴的位置就是正确的(即数组下标不会在发生改变了), 递归对两个子序列进行重新排序.

#include<stdio.h>

#define LEN 10

int a[LEN] = {

    10, 5, 3, 2, 1, 7, 8, 6, 9, 4

};

int position(int start, int end)

{

    int dp = start;

    int i = start; /* 左边指针 */

    int j = end;   /* 右边指针 */

    int temp;

    while (i < j) {

        for(; i<dp; i++) {

            if (a[i] > a[dp]) {

                temp = a[i];

                a[i] = a[dp];

                a[dp] = temp;

                dp = i;

            }   

        }

       

        for (; j>dp; j--) {

            if (a[j] < a[dp]) {

                temp = a[j];

                a[j] = a[dp];

                a[dp] = temp;

                dp = j;

            }   

        }

    }

    return dp;

       

}

void short_sort(int start, int end)

{

    int dp;

    dp = position(start, end);

    printf("\ndp location: %d\n", dp);

    if (start < end) {

        short_sort(start, dp-1);

        short_sort(dp+1, end);

    }   

}

int main(void)

{

    int i;

    short_sort(0, LEN-1);

    for (i=0; i<LEN; i++) {

        printf("%d, ", a[i]);

    }   

}

---

迷宫深度优先, 广度优先

参考本blog中的 栈和队列

深度优先 用栈实现

广度优先 用队列实现, 特别的地方是, 用栈实现的广度优先, 在入队列时, 要记录对应的上一步的位置, 因为它不同栈, 栈的上一步的位置是按照栈的先后顺序存储的.