数据结构(二)——排序

 

如上图，若两个5排序之后交换了位置就是不稳定的，没有交换位置就是稳定排序

 

1.选择排序

　　

 

　　冒泡是相邻的两个交换，选择法是首元素与最小的交换。

 1 void xuanzhepaixu(int* my_array, int len)
 2 {
 3     for (int i = 0; i < len - 1;   i) {
 4         for (int j = i   1; j < len;   j) {
 5             if (my_array[i] > my_array[j]) {// 交换次数多，不如记录下表位置效率高
 6                 int temp = my_array[i];
 7                 my_array[i] = my_array[j];
 8                 my_array[j] = temp;
 9             }
10         }
11 
12     }
13 }

 

 

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 // 选择法排序
 6 void xuanzhepaixu(int* my_array, int len)
 7 {
 8     int min = 0;
 9     for (int i = 0; i < len - 1;   i) {
10         min = i;
11         for (int j = i   1; j < len;   j) {
12             if (my_array[min] > my_array[j]) {
13                 min = j;// 保存最小元素的位置
14             }
15         }
16         if ( min != i ) {
17             int temp = my_array[i];
18             my_array[i] = my_array[min];
19             my_array[min] = temp;
20         }
21     }
22 }
23 
24 void my_print_array(int* my_array, int len)
25 {
26     for (int i = 0; i < len;   i) {
27         printf("]", my_array[i]);
28     }
29     printf("\n");
30 }
31 
32 int main()
33 {
34     int my_array[] = {10, 6, 7, 4, 9, 8, 5, 1, 3, 2};
35     int len = sizeof(my_array) / sizeof(int);
36 
37     xuanzhepaixu(my_array, len);
38 
39     my_print_array(my_array, len);
40 
41     system("pause");
42     return 0;
43 }

 

2.冒泡排序

 

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

 

冒泡算法的优化，在待排序数据处于一种趋于有序的情况，可以减少判断次数，比如：1，2，3，4，7，5，6

 1 void maopaopaixu(int* my_array, int len)
 2 {
 3     bool flag = false;
 4     for (int i = 0; i < len && !flag;   i) {
 5         flag = true;
 6         for (int j = 1; j < len;   j) {
 7             if ( my_array[j] > my_array[j - 1] ) {
 8                 int temp = my_array[j];
 9                 my_array[j] = my_array[j - 1];
10                 my_array[j - 1] = temp;
11                 flag = false;
12             }
13         }
14     }
15 }

 

3.插入排序

　　默认对两个序列进行操作：有序序列，无序序列。

　　可以将无序序列分为两个部分

 

void insert_paixu(int* my_array, int len)
{
    int temp = 0;// 存储基准数
    int index = 0; // 存储坑的位置

    for (int i = 1; i < len;   i) {
        temp = my_array[i];
        index = i;
        for (int j = i - 1; j >= 0; --j) {// 从后往前遍历
            if (temp < my_array[j]) {
                my_array[j   1] = my_array[j];
                index = j;
            }
            else break;//最后一个保存的是最大的元素，此语句可以减少判断
        }
        my_array[index] = temp;
    }
}

 

4.希尔排序

　　先分组，再对每组进行插入排序。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，算法便终止；