> 文档中心 > 八大排序(上)

八大排序(上)


📋 个人简介

  • 💖 作者简介:大家好,我是菀枯😜

  • 🎉 支持我:点赞👍+收藏⭐️+留言📝

  • 💬格言:不要在低谷沉沦自己,不要在高峰上放弃努力!☀️

    八大排序(上)

前言

☀️从今天开始,我们开始新的征程。首先我想和大家分享的就是最简单的算法之一:排序算法因为排序算法比较多,我会分为上下两部分,上半部分会和大家分享一些比较基础的排序算法。

冒泡排序

☁️首先,我们从最简单的排序算法,冒泡排序开始聊起。

什么是冒泡排序

☁️顾名思义,这个排序算法在排序数会通过不断的交换,将最小的元素慢慢“浮”到数列的顶端,就像一个在水里面的泡泡一样,会慢慢浮到水面上。

☁️接下来我们用一个动图来看看冒泡排序的排序过程:

  1. ☁️比较相邻的元素,如果前面的元素大于后面的元素,二者交换。
  2. ☁️对数组中的所有元素进行同样操作,可以确保最大元素移动到数组末尾
  3. ☁️然后对除了最后一个的所有元素重复之前的操作,将第二大的元素放到数组倒数第二位。
  4. ☁️重复之前的步骤,直到排序完成

八大排序(上)

冒泡排序的思想

☁️就是对于所有未排序的所有数,从前往后对相邻的两个数进行比较,大的数在不断的交换中,被放到了数组的后面。而小的数就被放到了数组的前面

☁️时间复杂度为: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;}}}}
  1. 对于所有的数,我们只需要走size - 1一次就可以将所有的数排序好。
  2. j < s i z e − 1 − i j < size - 1-i j<size1i 是因为之前的一趟,我们已经将最大的数放到末尾了,那么我们就不用再去排它了
  3. 如果相邻两数,后面的数小于前面的数,那么就交换二者。

插入排序

什么是插入排序

🍚插入排序就类似我们打扑克时,对手牌排序一样。选择一张牌,然后将它插到前面已经排序好的数列当中。

🍚接下来我们用一个动图来看看插入排序的排序过程:

  1. 🍚从第一个元素开始,可以认为它已经有序
  2. 🍚取出下一个元素,并在前面的有序区间中寻找插入位置
  3. 🍚将这个元素插入到正确的位置后,重复之前的步骤

八大排序(上)

插入排序几本思想

🍚就是保证前面的一段区间的元素为有序,然后将该区间面的元素不断插入到区间中,知道所有元素都已经插入到这段有序区间中。

🍚时间复杂度为: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. 有序区间的尾部
  2. 要插入到有序区间的元素
  3. 寻找插入元素的位置
  4. 将元素插入到前面的有序区间中1

希尔排序

什么是希尔排序

☀️希尔排序按其设计者希尔(Donald Shell)的名字命名,是唯一一个以人名来命名的排序方法。希尔排序是插入排序经过改良后的一种排序方法,也称作“缩小增量排序”。

☀️接下来我们用一个动图来看看希尔排序的排序过程:

  1. ☀️选择一个增量,然后根据这个增量,将数组中所有的元素分组
  2. ☀️分别对每个组进行插入排序
  3. ☀️不断减小增量,重复上面的步骤,直到增量为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]=2tk+11,(1kt[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;}}}
  1. 不断缩小增量,直到最后对所有元素进行插入排序
  2. 根据增量,分组进行排序。

选择排序

什么是选择排序

🌻选择排序是一种思路比较简单的排序,我们要找到数组中最小的元素,然后将其放在最前面,然后不断重复这个过程,就可以将数组变为有序。

🌻接下来我们用一个动图来看看选择排序的排序过程:

  1. 第一趟遍历,找到其中最小的元素。
  2. 然后最小的元素和第一个元素进行交换。
  3. 重复之前的步骤,直至数组有序。

八大排序(上)

选择排序基本思想

🌻每一趟在 n − i + 1 ( i = 1 , 2 , 3 , . . . , n − 1 ) n-i+1(i=1,2,3,...,n-1) ni+1(i=1,2,3,...,n1)个记录中选择最小的记录作为有序序列中第 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)}}
  1. 取后面无序序列的第一个元素为假设最小元素。
  2. 然后遍历后面找到最小元素。
  3. 将最小元素放到无序序列的最前面。

结语

欢迎各位参考与指导!!!❤️

八大排序(上)