冒泡，选择，插入，希尔排序

目录

一. 冒泡排序

1. 算法思想

2. 时间复杂度与空间复杂度

3. 代码实现

二. 选择排序

1. 算法思想

2. 时间复杂度与空间复杂度

3. 代码实现

三.插入排序

1. 直接插入排序

(1). 算法思想

(2). 时间复杂度与空间复杂度

(3). 代码实现

2. 希尔排序

(1). 算法思想

(2). 代码实现

(3). 时间复杂度与空间复杂度

一. 冒泡排序

1. 算法思想

假设排升序，从头开始两两比较选出最大的的值移到最后面（假设下标为10），再从头开始两两比较选出次大的移到下标为9的地方以此类推

2. 时间复杂度与空间复杂度

(1). 最优情况

当数据全都有序时，最快。因为此时每个元素只需比较一次就可以完成整个排序过程此时时间复杂度为   O(N)

(2). 最坏情况

当数据逆序时最慢，此时每一次比较都需要交换。时间复杂度为  O(N²)

(3). 平均情况

综上所述，平均复杂度为  O(N²)

(4). 空间复杂度

冒泡排序只需要一个额外变量来交换元素，不需要额外的数据结构来存储数据，所以空间复杂度为     O(1)

3. 代码实现

void BubbleSort(int* a, int n)//冒泡排序
{int count = 0;for(int j=0;j<n-1;j++){for (int i = 0; i < n - j-1; i++){if (a[i] <a[i+1] ){Swap(&a[i], &a[i + 1]);count = 1;}}if (count == 0)break;}
}

二. 选择排序

1. 算法思想

假设排升序，遍历数组，选出最大值与排序数列的最后一个元素（假设下标为10）交换，再从除最后一个元素（即下标0~9）的序列中找出次大值与下标为9的序列交换以此往复知道排序完毕

2. 时间复杂度与空间复杂度

(1). 时间复杂度

选择排序需要遍历n-1次来找到最小(或最大)元素，并且在每次遍历中都需要对剩余未排序元素进行遍历以找到最小(或最大)元素，因此选择排序的时间复杂度总是   O(N²)

(2) 空间复杂度

只需一个额外变量来存储找到的最大(或最小)元素的索引，所以空间复杂度为   O(1)

3. 代码实现

我们实现一个优化版本，同时找到最大的值与最小的值，分别与头和尾交换

void SelectSort(int* a, int n)
{int begin = 0, end = n -1;while(begin<end){int max = begin, min = begin;for (int i = begin+1; i <= end; i++){if (a[i] > a[max])max = i;if (a[i] < a[min])min = i;}Swap(&a[begin], &a[max]);Swap(&a[end], &a[min]);begin++;end--;}
}

以上代码还有一个小问题，当出现下图情况时

begin所指向的值与max所指向的值交换，那min指向的值就变为了原来max所指向的值，此时再与end交换会发生将最大的值交换过去的情况

修改代码为

void SelectSort(int* a, int n)
{int begin = 0, end = n -1;while(begin<end){int max = begin, min = begin;for (int i = begin+1; i <= end; i++){if (a[i] > a[max])max = i;if (a[i] < a[min])min = i;}if (begin == min){Swap(&a[begin], &a[max]);Swap(&a[max], &a[end]);}else{Swap(&a[begin], &a[max]);Swap(&a[end], &a[min]);}begin++;end--;}
}

三.插入排序

1. 直接插入排序

(1). 算法思想

从第一个元素开始排序，先排前一个数，再排前两个数以此类推

假设排升序，第一个数自然是有序的，第二个数与第一个数比较，如果比第一个数小就与其交换，然后看第三个数，此时前两个数是有序的，第三个数先于第二个数比较，比第二个数小就与其交换，再与第一个数比较，比第一个数小就与其交换，如果不比第二个数小就看第四个数，此时前三个数都是有序的以此类推

(2). 时间复杂度与空间复杂度

① 最好情况

在有序情况下只需遍历一遍即可时间复杂度为   O(N)

②最坏情况

在逆序情况下，每一次比较都要交换，时间复杂度为 O(N²)

③平均情况

综上所述平均时间复杂度为O(N²)

④空间复杂度

只需要一个额外的空间来存储当前要插入的元素，空间复杂度为O(1)

(3). 代码实现

void InsertSort(int* a,int n)//直接插入排序
{for(int i=0;i<n-1;i++){int end = i;int t = a[i+1];while (end >= 0){if (t < a[end]){a[end+1] = a[end];end--;}else   break;}a[end+1] = t;}}

2. 希尔排序

(1). 算法思想

是直接插入算法的改进版本，总体操作可大致分为两步

先进行预排序

直接插入排序

 直接插入排序是和距离为1的元素比较，而希尔排序是和距离为gap的元素比较，gap不断变小，直到变为1，此时即是直接插入排序

初始序列为 9 1 2 5 7 4 8 6 3 5 ，gap值为5进行一次预排序过程如下

预排序后序列为

当gap为2时

预排序后序列为

 我们发现预排序后一定比之前更加接近有序

从时间上讲，gap越大，大的数可以越快的到后面去，小的数可以越快的到前面去

gap越小呢，预排序完就越接近有序，gap==1就是直接插入排序

我们就可以将gap慢慢减少直到变为1从而进行直接插入排序是尽量是最好的情况

(2). 代码实现

希尔排序的代码与直接插入排序的代码十分相似，不同的地方就是gap，可以通过三层循环或四层循环实现，两者执行的次数实际是一样的

void ShellSort(int* a, int n)//希尔排序
{int gap = n;while(gap>1){gap =gap/ 3+1;// 除3不一定会=1，但3是最合理的，所以+1保证最后一次gap一定是1 //for(int j=0;j<gap;j++)//{for (int i = 0; i < n - gap; i++)//一组一组的排序所以i也可以+=gap，效率没有区别，都是要走这些步数{int end = i;int t = a[end + gap];while (end >= 0){if (t < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = t;}//}}
}

(3). 时间复杂度与空间复杂度

希尔时间复杂度的计算，需要很高的数学水平，此处只做粗略解释(我不会，嘿嘿)

①时间复杂度

我们假设每一次gap=n/3,此时每组三个数据，

最坏情况下 第一次排序消耗：(1+2)*n/3==n

下一次 

gap=n/3/3=n/9，每组9个数据

但此时由于上面的预排序，不可能是最坏情况，即

(1+2+3+4+5+6+7+8)*n\9

具体计算我也不会

但是最后一次，gap==1时(此时很接近有序)

直接插入排序消耗n

时间复杂度大致为  O(N^1.3)即N的1.3次方

②空间复杂度

由于不需要额外的空间，所以空间复杂度为O(1)

---

这篇文章就到这里啦

(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤