插入排序、冒泡排序、选择排序——转载

本文首先介绍几种通过交换相邻元素进行排序的算法:插入排序,冒泡排序,选择排序;之后会分析通过交换相邻元素进行排序的算法的时间界。

下文将假设待排序的数组的元素为 : 34,8,64,51,32,21。 待排序的元素的个数为 N。

插入排序:

简介:

插入排序最实际的一个例子就是我们玩纸牌的时候,我们都会保持手中的牌是有序的,当拿到一张新的牌时,将它插入到合适的位置。在将新牌插入到合适的位置的时候,我们会拿它同我们手中的牌,从右到左依次比较,直到找到合适的位置。在每次把新牌插入到合适的位置后,我们手中的牌总是有序的。这也是插入排序的基础。如下图所示:

 

排序过程:

插入排序需要进行N-1趟排序。在排序过程中,会将原始数组分为两部分,前半部分是排好序的,后半部分则还是原序。每一趟排序都是以前半部分已排好序为基础的,即: 在进行第 i(i>=1 and i<=N-1)趟排序时,位置0到位置i-1上的元素都已排好序。每一趟排序结束,都会使已排好序的前半部分增加一个元素,后半部分减少一个元素。下面以图的形式说明:

 

 

实现:排序过程中要保持如下不变式:在进行第i (i>=1 && i<N-1) 趟排序时,要保证前半部分,即位置0到位置i上的元素是有序的。

首先第一趟排序之前,前半部分只包含一个元素,array[0], 因此是有序的;之后在每次循环中,我们要保持此不变式。

public static void insertSorting(int array[]){         //需要排序的趟数         int sortTime = array.length - 1;         /开始时,前半部分只包含一个元素 array[0],从而循环开始的时候, 不变式array[0] <= .... <= array[i]为真/         for (int i = 1; i <= sortTime; i++){             //第i趟排序中待插入到前半部分正确位置上的元素             int tmp = array[i];             int j = i;             //待插入到正确位置上的元素,和前半部分元素,从右到左依次比较,如果小于前半部分的元素,则交换             for (; j>0 && array[j-1]>tmp; j--){                 array[j] = array[j-1];             }             array[j] = tmp;             /保证了位置0到位置i上的元素是有序的,不变式得以保持/         }     }

复杂度:时间复杂度为O(N^2), 空间复杂度为 O(1)。

 

冒泡排序:

简介:

冒泡排序最形象的一个比喻就是,在水中的气泡(因为最轻)会慢慢的浮到水面。这也说明了冒泡排序的原理:依次比较相邻的元素,从开始的一对元素到最后的一对元素,如果元素的顺序错误则交换,从而在比较了所有的元素后,最大的元素则“浮”到数组的末尾。重复此过程,直到排序完成。

排序过程:

冒泡排序也需要N-1趟排序(可以通过额外的标记,在没有元素交换时,提前结束排序)。在排序过程中,也将数组分为两部分,前半部分是无序的,后半部分则是有序的。开始时,前半部分为整个数组。在每一趟排序中,都从前半部分数组,按照从第一个元素到最后一个元素的顺序,依次比较相邻的两个元素。如果两个元素的顺序不正确,则交换两个元素的位置。每一趟排序完成时,前半部分数组的最后一个元素为前半部分数组中最大的一个。从而,后半部分排好序的数组增加一个元素,前半部分乱序的子数组减少一个元素,以此类推。下图说明了一趟排序过程:

实现:

1 2 3 4public static void bubbleSort(int array[]){ 5 6 7 8        int sortTime = array.length - 1; 9 10 11 12        int tmp; 13 14 15 16        for (int i = sortTime; i > 0; i--){ 17 18 19 20            // 每一次循环都会将最大的元素放在 数组的 i 索引处 21 22 23 24            for (int j = 0; j < i; j++){ 25 26 27 28                //两个元素的位置错误,则交换 29 30 31 32                if (array[j] > array[j+1]){ 33 34 35 36                    tmp = array[j]; 37 38 39 40                    array[j] = array[j+1]; 41 42 43 44                    array[j+1] = tmp; 45 46 47 48                } 49 50 51 52            } 53 54 55 56        } 57 58 59 60    } 61 62 63

复杂度:时间复杂度为O(N^2),空间复杂度为O(1)。

 

选择排序:

简介:

选择排序的思想是最简单的,每次从数组中待排序的部分重选择一个最小的元素,放在对应的位置;重复此过程...

排序过程:

选择排序也将原始数组分为两部分,前面是排好序的子数组,后半部分则是乱序的。首先,前面的有序子数组为空,乱序部分为整个数组。我们需要在乱序的部分中选择一个最小的元素,之后和乱序部分的第一个元素交换;此时,前半部分的有序子数组增加了一个元素,后半部分的乱序子数组则减少一个元素;以此类推。

实现:

1 2 3 4public static void selectSort(int array[]){ 5 6 7 8        int length = array.length - 1; 9 10 11 12        int tmpMin; 13 14 15 16        for (int i = 0; i < length; i++){ 17 18 19 20            int minIndex = i; 21 22 23 24            for (int j = i + 1; j <= length; j++){ 25 26 27 28                if (array[minIndex] > array[j]){ 29 30 31 32                    minIndex = j; 33 34 35 36                } 37 38 39 40            } 41 42 43 44            if (i != minIndex){ 45 46 47 48                tmpMin = array[i]; 49 50 51 52                array[i] = array[minIndex]; 53 54 55 56                array[minIndex] = tmpMin; 57 58 59 60            } 61 62 63 64        } 65 66 67 68    } 69 70 71

复杂度: 时间复杂度为O(N^2),空间复杂度为O(2)。

下面说明,通过交换相邻元素的排序算法的平均运行时间为N(N-1)/4

数组中的一个逆序是指数组中具有性质 i < j 但是 A[i] > A[j]的一个序偶。例如:34,8,64,51,32,21有9个序偶  即 (34,8) (34,32) (34,21)  (64,51) (64,32) (64,21) (51,32) (51,21) (32,21)。这也是 通过交换相邻元素的排序算法 需要执行的交换次数。 因为交换两个不按原序排列的相邻元素正好消除一个逆序,而一个排序的数组是没有逆序的。

对于任意的数的一个列表L,考虑其反序表Lr  如 21,32,51,64,8,34 。 考虑这个表中任意的两个数的序偶(x,y) 且 x > y ,显然 这个序偶恰好存在于表L或 Lr 中的一个。  该序偶对应一个逆序 。 在列表L和 反序表 Lr中,这样的序偶的总个数为 N(N-1)/2,  表L中的这样的序偶平均是该量的一半 , 所以表l平均有 N(N-1)/4个逆序。

上文说过,交换两个不按原序排列的相邻元素 正好消除一个逆序 。所以只通过交换相邻元素进行排序的排序算法平均需要 N(N-1)/4时间。

插入排序和冒泡排序通过交换相邻的元素进行排序比较明显,但是选择排序在内循环中正是通过对相邻元素的比较,才选择出了最小元素的下标,从而在接下来的交换操作中,消除了涉及到该最小元素的所有逆序。

只进行相邻元素的交换每次只能消除一个逆序,**  如果对于相距较远的元素进行交换,  则有望每次交换消除不止一个逆序。  这就是接下来要介绍的shell****排序的情况**。

参考文献:数据结构与算法分析,算法导论,编程珠玑。

 

代码交流 2021