八大排序(上)
📋 个人简介
-
💖 作者简介:大家好,我是菀枯😜
-
🎉 支持我:点赞👍+收藏⭐️+留言📝
-
💬格言:不要在低谷沉沦自己,不要在高峰上放弃努力!☀️
前言
☀️从今天开始,我们开始新的征程。首先我想和大家分享的就是最简单的算法之一:排序算法因为排序算法比较多,我会分为上下两部分,上半部分会和大家分享一些比较基础的排序算法。
冒泡排序
☁️首先,我们从最简单的排序算法,冒泡排序开始聊起。
什么是冒泡排序
☁️顾名思义,这个排序算法在排序数会通过不断的交换,将最小的元素慢慢“浮”到数列的顶端,就像一个在水里面的泡泡一样,会慢慢浮到水面上。
☁️接下来我们用一个动图来看看冒泡排序的排序过程:
- ☁️比较相邻的元素,如果前面的元素大于后面的元素,二者交换。
- ☁️对数组中的所有元素进行同样操作,可以确保最大元素移动到数组末尾
- ☁️然后对除了最后一个的所有元素重复之前的操作,将第二大的元素放到数组倒数第二位。
- ☁️重复之前的步骤,直到排序完成
冒泡排序的思想
☁️就是对于所有未排序的所有数,从前往后对相邻的两个数进行比较,大的数在不断的交换中,被放到了数组的后面。而小的数就被放到了数组的前面
☁️时间复杂度为:O (n2 ) O(n^2) O(n2)
C语言实现
void BubbleSort(int* a, int size){for (int i = 0; i < size - 1; i++) // (1){for (int j = i; j < size - 1 - i; j++) // (2){if (a[j] > a[j + 1]) // (3){int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;}}}}
- 对于所有的数,我们只需要走
size - 1
一次就可以将所有的数排序好。 - j < s i z e − 1 − i j < size - 1-i j<size−1−i 是因为之前的一趟,我们已经将最大的数放到末尾了,那么我们就不用再去排它了
- 如果相邻两数,后面的数小于前面的数,那么就交换二者。
插入排序
什么是插入排序
🍚插入排序就类似我们打扑克时,对手牌排序一样。选择一张牌,然后将它插到前面已经排序好的数列当中。
🍚接下来我们用一个动图来看看插入排序的排序过程:
- 🍚从第一个元素开始,可以认为它已经有序
- 🍚取出下一个元素,并在前面的有序区间中寻找插入位置
- 🍚将这个元素插入到正确的位置后,重复之前的步骤
插入排序几本思想
🍚就是保证前面的一段区间的元素为有序,然后将该区间面的元素不断插入到区间中,知道所有元素都已经插入到这段有序区间中。
🍚时间复杂度为:O (n2 ) O(n^2) O(n2)
C语言实现插入排序
void InsertSort(int* a, int size){for (int i = 0; i < size - 1; i++){int end = i;//(1)int tmp = a[end + 1];//(2)while (end >= 0){if (tmp < a[end]) //(3){a[end + 1] = a[end];end -= 1;}else{break;}}a[end + 1] = tmp; //(4)}}
- 有序区间的尾部
- 要插入到有序区间的元素
- 寻找插入元素的位置
- 将元素插入到前面的有序区间中1
希尔排序
什么是希尔排序
☀️希尔排序按其设计者希尔(Donald Shell)的名字命名,是唯一一个以人名来命名的排序方法。希尔排序是插入排序经过改良后的一种排序方法,也称作“缩小增量排序”。
☀️接下来我们用一个动图来看看希尔排序的排序过程:
- ☀️选择一个增量,然后根据这个增量,将数组中所有的元素分组
- ☀️分别对每个组进行插入排序
- ☀️不断减小增量,重复上面的步骤,直到增量为1.
希尔排序的基本思想
☀️先将整个待排序列分割成为若干个子序列分别进行插入排序,待整个序列中的元素“基本有序”时,再对所有元素进行一次插入排序。
☀️时间复杂度:希尔排序的时间复杂度较为难算,它的时间复杂度与增量的大小有关。当
Δ [ k ] =2 t − k + 1 − 1 , ( 1 ≤ k ≤ t ≤ [ log 2 ( n + 1 ) , 其 中 t 为 排 序 趟 数 ] ) \Delta [k] = 2^{t-k+1}-1,(1\le k \le t \le [\log_2(n+1),其中t为排序趟数]) Δ[k]=2t−k+1−1,(1≤k≤t≤[log2(n+1),其中t为排序趟数])
时,希尔排序的时间复杂度为* O ( n32 ) O(n^{\frac{3}{2}}) O(n23)*
C语言实现希尔排序
void ShellSort(int* a, int size){int gap = size;while (gap > 1){gap = gap / 3 + 1 ; //(1)for (int i = 0; i < size - gap; i++) //(2){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
- 不断缩小增量,直到最后对所有元素进行插入排序
- 根据增量,分组进行排序。
选择排序
什么是选择排序
🌻选择排序是一种思路比较简单的排序,我们要找到数组中最小的元素,然后将其放在最前面,然后不断重复这个过程,就可以将数组变为有序。
🌻接下来我们用一个动图来看看选择排序的排序过程:
- 第一趟遍历,找到其中最小的元素。
- 然后最小的元素和第一个元素进行交换。
- 重复之前的步骤,直至数组有序。
选择排序基本思想
🌻每一趟在 n − i + 1 ( i = 1 , 2 , 3 , . . . , n − 1 ) n-i+1(i=1,2,3,...,n-1) n−i+1(i=1,2,3,...,n−1)个记录中选择最小的记录作为有序序列中第 i i i个记录。
🌻时间复杂度: O (n2 ) O(n^2) O(n2)
C语言实现选择排序
void SelectSort(int* a, int size){for (int i = 0; i < size - 1; i++){int min = a[i]; //(1)for (int j = i; j < size; j++) //(2){if (min > a[j]){int tmp = min;min = a[j];a[j] = tmp;}}a[i] = min; //(3)}}
- 取后面无序序列的第一个元素为假设最小元素。
- 然后遍历后面找到最小元素。
- 将最小元素放到无序序列的最前面。
结语
欢迎各位参考与指导!!!❤️