八大排序原来也不过如此

2024-09-07 23:36
文章标签 排序 八大 原来 不过如此

本文主要是介绍八大排序原来也不过如此，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

详解八大排序

  • 前言
  • 1.插入排序
    • 1.1 直接插入排序
    • 1.2 希尔排序
  • 2.选择排序
    • 2.1 选择排序
    • 2.2 堆排序
  • 3. 交换排序
    • 3.1 冒泡排序
    • 3.2 快排
      • 3.2.1 hoare版本
      • 3.2.2 挖坑版本
      • 3.2.3 双指针版本
      • 3.2.4 快排优化
      • 3.3.5 快排时间复杂度和空间复杂度分析
      • 3.2.5 非递归实现快排
  • 4. 归并排序
    • 4.1 递归实现
    • 4.2 非递归实现
  • 5. 计数排序
  • 6. 总结

在这里插入图片描述

所属专栏：初始数据结构❤️
🚀 >博主首页：初阳785❤️
🚀 >代码托管：chuyang785❤️
:roc0ket: >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️
🚀 >博主也会更加的努力，创作出更优质的博文！！❤️
🚀 >三连，三连，三连0，重要的事情说三遍！！！！！！！！❤️

前言

  • 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
    排序在我们生活当中随处可见。我们在手机上买东西，可以按照价格排序，也可以根据销量排序来选择我们心仪的商品。再如我们学的考试成绩，排名之类的排序，等等等。
  • 总的一句话就是，排序在生活中很重要。

1.插入排序

1.1 直接插入排序

  • 直接插入排序是一种简单的插入排序法，其基本思想是：
    把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
    实际中我们玩扑克牌时，就用了插入排序的思想
    在这里插入图片描述
//1.直接插入排序
void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int tmp = a[i + 1];int cur = i;while (a[cur] > tmp && cur >= 0){a[cur + 1] = a[cur];cur--;}a[cur + 1] = tmp;}
}

动态展示图：
在这里插入图片描述

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定

1.2 希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序序列中所有记录分成若干个子序列，所有距离为所选定的整数gap记录的分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达gap=1时，所有记录在进行一次直接插入排序。

在这里插入图片描述

//2. 希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//gap = gap / 3 + 1;这里是根据研究表明除于3是有更快的速度，这里为了便于讲解使用除2gap = gap / 2;for (int i = 0; i < n - gap; i++){int tmp = a[i + gap];int cur = i;while (a[cur] > tmp && cur >= 0){a[cur + gap] = a[cur];cur -= gap;}a[cur + gap] = tmp;}}

动态图展示：
在这里插入图片描述

希尔排序的特性总结：

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定.

《数据结构(C语言版)》— 严蔚敏在这里插入图片描述

《数据结构-用面相对象方法与C++描述》— 殷人昆
在这里插入图片描述

  1. 稳定性：不稳定

2.选择排序

2.1 选择排序

  • 基本思想：
    每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
  • 直接选择排序:
    在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
//3. 选择排序
void SelectSort1(int* a, int n)
{for (int i = 0; i < n; i++){int tmp = i;for (int j = i + 1; j < n; j++){if (a[j] < a[tmp]){tmp = j;}}Swap(&a[i], &a[tmp]);}
}

动态图展示：
在这里插入图片描述
这里我们做一下优化，同时找到最大值和最小值进行交换：

void SelectSort2(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min_idx = begin;int max_idx = end;for (int i = begin; i <= end; i++){if (a[i] < a[min_idx]){min_idx = i;}if (a[i] > a[max_idx]){max_idx = i;}}Swap(&a[begin], &a[min_idx]);//这里要做处理，如果max_idx处于begin的位置的话，因为上一段代码Swap(&a[begin], &a[min_idx]);//已经吧原来的数交换到min_idx的位置的，所以这里要重新定位if (max_idx == begin){max_idx = min_idx;}Swap(&a[end], &a[max_idx]);begin++;end--;}
}

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

2.2 堆排序

  • 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
  • 注：如果有对堆还不清楚的前面我出了一期关于二叉树的内容，里面有详细讲解堆，二叉数等性质，不清楚的小伙伴可以看看
    在这里插入图片描述
void AdjustDwon(int* a, int n, int root)
{int child = root * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[child] > a[root]){Swap(&a[child], &a[root]);root = child;child = root * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//向下调整键大堆for (int i = (n - 2) / 2; i >= 0; i--){AdjustDwon(a, n, i);}PrintfSort(a, n, "SelectSort2");int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDwon(a, end, 0);end--;}
}

动态图展示：
在这里插入图片描述

直接选择排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

3. 交换排序

  • 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
    序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.1 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。（相邻对比交换位置）

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

动态图展示：
在这里插入图片描述

冒泡排序的特性总结：

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

3.2 快排

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

3.2.1 hoare版本

方法步骤：

  1. 设置一个基准值，这里拿的是第一个数据为基准值
  2. 目的是左边的所有数都是小于等于基准值的，右边的数都是大于等于基准值的。
  3. 两个while循环左边直到找到大于基准值就停下，右边直到找到小于基准值就停下，最后进行交换
  4. 最后记得不要忘记将基准值放到分界位置，在进行递归处理

动态图
在这里插入图片描述

写法一：

//快排
//hoare版本
void QuickSortHoare(int* a, int left, int right)
{if (left >= right)return;int l = left;int r = right;int key = left;while (l < r){// 注意这里必须是<= / >= 不能是 < / > 因为如果a是1 1 1 1 1重复的数组元素的话，就会陷入死循环while (l < r && a[r] >= a[key]){r--;}while (l < r && a[l] <= a[key]){l++;}Swap(&a[l], &a[r]);}Swap(&a[left], &a[r]);QuickSortHoare(a, left, r - 1);QuickSortHoare(a, r + 1, right);
}

写法二：

void QuickSortHoare(int* a, int left, int right)
{if (left >= right)return;int l = left;int r = right;int key = (left + right) >> 1;while (l < r){// 注意这里必须是<= / >= 不能是 < / > 因为如果a是1 1 1 1 1重复的数组元素的话，就会陷入死循环while (a[r] > a[key]){r--;}while ( a[l] < a[key]){l++;}if (l <= r){Swap(&a[l], &a[r]);l++;r--;}}QuickSortHoare(a, left, r);QuickSortHoare(a, l, right);
}

3.2.2 挖坑版本

其实挖坑法和上米娜的hoare版本的步骤是一样的，只不过将交换的动作使用填补法进行替换了。

动态图：
在这里插入图片描述

void QuickSortDig(int* a, int left, int right)
{if (left >= right)return;int l = left;int r = right;int key = a[left];while (l < r){// 注意这里必须是<= / >= 不能是 < / > 因为如果a是1 1 1 1 1重复的数组元素的话，就会陷入死循环while (l < r && a[l] <= key){l++;}a[r] = a[l];while (l < r && a[r] >= key){r--;}a[l] = a[r];}a[l] = key;QuickSortHoare(a, left, l - 1);QuickSortHoare(a, l + 1, right);
}

3.2.3 双指针版本

实现方法：

  1. 我们的目的是将基准值左边的数都小于等于基准值，右边的数都小于等于基准值。
  2. 于是我们就可以定义两个变量prev和cur，cur一直往下遍历，直到遇到小于基准值的就停下，这个时候将cur的数据和prev的数据进行交换。
  3. 因为只有当cur遇到小于基准值的数据才会停下，并且才会和prev进行交换，也就是说prev走过的地方的数据都是小于基准值的数据，也就是说prev其实就是那个临界点。

动态图：
在这里插入图片描述

void QuickSortPoint(int* a, int left, int right)
{if (left >= right)return;int key = left;int prev = left;int cur = prev + 1;while (cur <= right) // 注意这里必须是<=，因为right位置也是一个元素也需要进行对比{if (a[cur] < a[key]){prev++;Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[key], &a[prev]);QuickSortPoint(a, left, prev - 1);QuickSortPoint(a, prev + 1, right);
}

3.2.4 快排优化

  1. 三数取中法

有的时候我们需要排序的数据可能已经接近有序的了，那么如果我们还用前面的快排进行排序的话事件复杂度将会达到O（N^2），因为我们设置的基准值都是从数据的一端开始的，所以我们就可以使用一种算法，我们不取一端的值，而是取中间值作为基准值。

int GetMid(int* a, int left, int right)
{int mid = (right + left) >> 1;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;else if (a[left] > a[right])return left;elsereturn right;}else//a[mid] > a[left]{if (a[right] > a[mid])return mid;else if (a[left] > a[right])return left;elsereturn right;}
}
void QuickSort1(int* a, int left, int right)
{if (left >= right)return;int mid = GetMid(a, left, right);Swap(&a[left], &a[mid]);int l = left;int r = right;int key = left;while (l < r){while (a[r] >= a[key] && l < r)r--;while (a[l] <= a[key] && l < r)l++;Swap(&a[l], &a[r]);}Swap(&a[left], &a[l]);QuickSort1(a, left, l - 1);QuickSort1(a, l + 1, right);
}
  1. 小区间使用非递归排序

到我们的数据量过多的时候，如果我们使用快排进行排序的话，注定时会有更深的递归深度，相应的栈空间的开销也会随之增大。并且当我们递归到一定的深度的时候，其实已经时接近有序了。所以这个时候其实我们可以不使用递归再往后进行排序了，而是使用插入排序进行排序。也就是说，当递归到一定的深度时候我们不适用递归进行排序了，而是使用其他排序的算法进行排序，因为快排时对范围内的数据进行排序，所以对于这部分范围的数据我们可以选择性的使用其他排序算法进行排序。这个样将多种算法进行混合式的使用可以大大提高算法的时间复杂度。

//部分快排，部分归插入
void QuickSort2(int* a, int left, int right)
{if (left >= right)return;int l = left;int r = right;int key = left;while (l < r){while (a[r] >= a[key] && l < r){r--;}while (a[l] <= a[key] && l < r){l++;}Swap(&a[l], &a[r]);}Swap(&a[left], &a[l]);if ((right - left + 1) > 10){PartSort1(a, left, l - 1);PartSort1(a, l + 1, right);}else{InsertSort(a + left, right - left + 1);}
}
  1. 三路划分

虽然三数取中法能解决待排序序列有序或接近有序的情况，但是如果序列中有大量的元素和key相等，甚至整个序列所有元素都相等时，三数取中也无法解决这种情况。

在这里插入图片描述

void QuickSortPath(int* a, int left, int right)
{if (left >= right)return;int key = a[left];int begin = left;int end = right;int cur = begin + 1;while (cur <= right){if (a[cur] < key){Swap(&a[begin], &a[cur]);begin++;cur++;}else if (a[cur] > key){Swap(&a[cur], &a[end]);end--;}else{cur++;}}QuickSortPath(a, left, begin - 1);QuickSortPath(a, end + 1, right);
}

3.3.5 快排时间复杂度和空间复杂度分析

  1. 时间复杂度

快排的时间复杂度是O（N*log2N）~O（N^2）

  1. 空间复杂度

因为空间的是可以重复使用的，函数结束调用之后会将创建的栈帧销毁根据快排代码的基本思路是先将key的左区间排完序，再去将key的右区间排有序那么根据代码思路它是一层一层递归，不断地选key，不断地将选出来的key的左区间缩小当左区间不能再分割时，递归就开始往回返，销毁栈帧，开始排右区间排右区间用的栈帧是刚刚左区间销毁的所以从宏观来看左区间的数排完栈帧全部销毁之后，右区间继续用之前销毁的空间所以空间复杂度就为高度。也即是O（log2N);

3.2.5 非递归实现快排

递归的思想其实和栈的思想是一样的，而这里快排其实就是根据数据下标的范围来来进行排序的。所以这里我们需要模拟的其实就是怎么保存排序的数据范围下标。

int SingSort(int* a, int left, int right)
{if (left >= right)return;int l = left;int r = right;int key = left;while (l < r){while (a[r] >= a[key] && l < r){r--;}while (a[l] <= a[key] && l < r){l++;}Swap(&a[l], &a[r]);}Swap(&a[left], &a[l]);return l;
}void QuickSortNonR(int* a, int left, int right)
{stack st;// 遵循stack的规则，先进的后出
// 先进右范围，在进左范围，这样拿出来就是先拿左，在拿右st.push(right);st.push(left);while (!st.empty()){int l = st.top();st.pop();int r = st.top();st.pop();int key = SingSort(a, l, r);// 进范围，同样遵循先进右，再进左if (key + 1 < r){st.push(r);st.push(key + 1);}if (key - 1 < l){st.push(key - 1);st.push(l);	}}
}

4. 归并排序

4.1 递归实现

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

在这里插入图片描述

动态图：

在这里插入图片描述
实现思路：

（1）malloc一块和待排序序列大小相同的空间，用来临时存放归并后的序列

（2）通过递归或迭代将待排序序列拆分多个子序列

（3）子序列间两两归并到开辟出的空间中，具体操作可以参考两个有序数组合并

（4）将归并后的子序列用memcpy覆盖到原序列中

（5）重复上述操作直到序列有序

void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)return;int mid = (left + right) >> 1;// 拆分_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);// 合并int k = left;int l = left;int r = mid + 1;while (l <= mid && r <= right){if (a[l] < a[r]){tmp[k++] = a[l++];}else{tmp[k++] = a[r++];}}while (l <= mid){tmp[k++] = a[l++];}while (r <= right){tmp[k++] = a[r++];}// 将合并后的结果拷贝回去memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(a) * n);if (NULL == tmp){printf("%s\n", "malloc error");}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

4.2 非递归实现

大体步骤：

  1. 设定一个初始值为1的gap
  2. 通过gap来分割子序列，每次分割出相邻的两个子序列，并进行合并成一个子序列。
  3. 重复2步骤直到遍历整个数组，将该次合并的结果覆盖原来的数组。
  4. 对gap进行更新，变成原来的2倍
  5. 重复2操作。

非递归需要解决两个越界问题
在这里插入图片描述

在这里插入图片描述

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);int gap = 1;while (gap < n){for (int i = 0; i < n; i += gap * 2){int left1 = i, right1 = i + gap - 1;int left2 = i + gap, right2 = i + gap * 2 - 1;int k = i;if (right1 >= n || left2 >= n){break;}if (right2 >= n){right2 = n - 1;}while (left1 <= right1 && left2 <= right2){if (a[left1] < a[left2]){tmp[k++] = a[left1++];}else{tmp[k++] = a[left2++];}}while (left1 <= right1){tmp[k++] = a[left1++];}while (left2 <= right2){tmp[k++] = a[left2++];}memcpy(a + i, tmp + i, sizeof(int) * (right2 - i + 1));}gap *= 2;}
}

5. 计数排序

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

实现步骤：

  1. 先遍历整个数组，找到最大值和最小值，确定数组范围。
  2. 根据数据范围开辟一个新的数组用来计数
  3. 遍历整个数组，将数据插入新开的数组（哈希桶）
  4. 根据哈希桶的下标顺序即可进行排序。

在这里插入图片描述

void CountSort(int* a, int n)
{int max = a[0];int min = a[0];for (int i = 0; i < n; i++){if (a[i] > max)max = a[i];if (a[i] < min)min = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);memset(count, 0, sizeof(int) * range);for (int i = 0; i < n; i++){count[a[i] - min]++;}int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

6. 总结

从上述的排序中我们可以大致得出每个排序的时间复杂度，以及稳定性

在这里插入图片描述

这篇关于八大排序原来也不过如此的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1146479。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
鸡尾酒排序算法

鸡尾酒排序算法

目录 引言 一、概念 二、算法思想 三、图例解释 1.采用冒泡排序：   2.采用鸡尾酒排序：  3.对比总结 四、算法实现  1.代码实现  2.运行结果 3.代码解释   五、总结 引言 鸡尾酒排序（Cocktail Sort），也被称为双向冒泡排序，是一种改进的冒泡排序算法。它在冒泡排序的基础上进行了优化，通过双向遍历来减少排序时间。今天我们将学习如何在C
阅读更多...
快速排序（java代码实现）

快速排序（java代码实现）

简介： 1.采用“分治”的思想，对于一组数据，选择一个基准元素，这里选择中间元素mid 2.通过第一轮扫描，比mid小的元素都在mid左边，比mid大的元素都在mid右边 3.然后使用递归排序这两部分，直到序列中所有数据均有序为止。 public class csdnTest {public static void main(String[] args){int[] arr = {3,
阅读更多...
O(n)时间内对[0..n^-1]之间的n个数排序

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内，对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,
阅读更多...
常用排序算法分析

常用排序算法分析

1. 插入排序 1.1 性能分析 时间复杂度O(n^2), 空间复杂度O(1) 排序时间与输入有关：输入的元素个数；元素已排序的程度。 最佳情况，输入数组是已经排好序的数组，运行时间是n的线性函数； 最坏情况，输入数组是逆序，运行时间是n的二次函数。 1.2 核心代码 public void sort(){int temp;for(int i = 1; i<arraytoSort.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2