各种排序算法的时间复杂度和空间复杂度.docx

文档介绍：各种排序算法的时间复杂度和空间复杂度
F
- - 入序_ 插排
入 播 接 a
O
定 稳
O
ofu
0(
不
选掙
XJ-
0(
5
定 稳 不各种排序算法的时间复杂度和空间复杂度
F
- - 入序_ 插排
入 播 接 a
O
定 稳
O
ofu
0(
不
选掙
XJ-
0(
5
定 稳 不
序 堆
^J.
定 稳 不
0(
n2)
定 稳
no
定 總 不
0
序 排 数 基
其中冒泡排序加个标志，所以最好情况下是o(n)
直接选择排序：
排序过程：
1 、首先在所有数据中经过n-1次比较选出最小的数，把它与第1个数据交换， 2、然后在其余的数据内选出排序码最小的数，与第 2个数据交换 依次类推，直
到所有数据排完为止。
在第i趟排序中选出最小关键字的数据，需要做n-i次比较。
1//冒泡排序，大的数不断向后冒泡
2void buddle(vector<int>& nums)
3{
int len=();
for(int i=0;i<len-1;i++)
6{
7 for(int j=0;j<len-1-i;j++)
8{
9
10
11
12
if(nums[j]>nums[j+1])
swap(nums[j],nums[j+1]);
13
14}
线性排序算法
计数排序
假设：有n个数的集合，而且n个数的范围都在O~k(k = O(n))之间。
运行时间：®(n+k)
，需要辅助数组B(存储最后排序结果)，数组C(存储元素的个数)。基于上 述的假设，数组C的大小为k, C[i]表示数组A中元素i(0 <= i < k)的个数()，为了保 证计数排序的稳定性，, C[i]表示小于或者等于i的个数。代码如下：
1: /*
2: 输入：待排序数组A,存储排序后的数组B，数组A的大小，数组C的大小
3: 功能：计数排序
4: */
5: void CountingSort(int A[], int B[], int len, int k)
6: {
7: int *CountArr = new int[k];
8: int i;
9: for (i = 0; i < k; i++)
10: {
11: CountArr[i] = 0;
12: }
13:
14: for (i = 0; i < len; i++)
15: {
16: CountArr[A[i]]++;
17: }
18:
19: for (i = 1; i < k; i++)
20: {
21: CountArr[i] += CountArr[i-1];
22: }
23:
24: // 从右至左保证算法的稳定性
25: for (i = len-1; i >=0; i--)
26: {
27: B[Cou