爱喝茶的仙人掌

Try to write something.

排序算法总结

Posted on Edited on In Views: Valine:
Symbols count in article: 5.7k Reading time ≈ 5 mins.
排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 稳定性
插入排序 \(O(n^2)\) \(O(n^2)\) \(O(1)\) 稳定
希尔排序 \(O(n^{1.3})\) \(O(n^2)\) \(O(1)\) 不稳定
快速排序 \(O(nlogn)\) \(O(n^2)\) \(O(logn)\) 不稳定
冒泡排序 \(O(n^2)\) O\((n^2)\) \(O(1)\) 稳定
选择排序 \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定
堆排序 \(O(nlogn)\) \(O(nlogn)\) \(O(1)\) 不稳定
归并排序 \(O(nlogn)\) \(O(nlogn)\) \(O(n)\) 稳定
基数排序 \(O(d(n+r))\) \(O(d(n+r))\) \(O(r)\) 不稳定

插入排序

插入排序的思想是每次将一个待排序列的元素按其关键字大小插入到前面已排好的序列中去，直到全部记录插入完成。

直接插入排序

算法思想及描述：

将待排序列逻辑结构分为前半部分有序（开始时前半部分元素个数为一），后半部分无序。

步骤：

  1. 选取无序部分的第一个元素；
  2. 逐步向前比较查找插入位置，并把已排序部分元素逐步向后移位；
  3. 直到找到插入位置，为一趟插入排序；
  4. 循环次数为无序序列的元素个数，在当前环境下为\(n-1\)。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(int A[], int n) {
  int i, j;
  for(i = 2; i <=n; i++) { //依次将A[2]~A[n]插入到已排序序列
    if (A[i] < A[i - 1]) { //元素值小于其前驱，需要进行插入操作
      A[0] = A[i]; //A[0]为哨兵位，不存放元素，暂存元素
      for(j = i - 1; A[0] < A[j]; --j) {
        A[j + 1] = A[j]; //后移操作
      }
      A[j+1] = A[0]; //复制到插入位置
    }
  }
}

时间复杂度分析：

最好情况下：表中元素已经有序，每插入一个元素都只需要比较一次而不需要移动元素，时间复杂度为\(O(n)\)。

最坏情况下：表中元素逆序，总的比较次数达到最大：\(\sum_{i=2}^{n}i\)，总的移动次数达到最大：\(\sum_{i=2}^{n}(i+1)\)

综上，时间复杂度为\(O(n^2)\)。

特点：

  1. 直接插入排序是稳定的排序算法。
  2. 直接插入排序适用于顺序存储和链式存储的线性表。
  3. 以此为基础引入折半插入排序，减少了查找元素时的比较次数，约为\(O(nlog_{2}n)\)，移动次数却没有改变，时间复杂度仍为\(O(n^2)\)。适用于数据量不是很大的排序表。

希尔排序

算法思想及描述：

从前面的分析可知，直接插入排序算法的时间复杂度为\(O(n^2)\)，但若待排序列为“正序”时，其时间复杂度可提高至\(O(n)\)，由此可见它更适用于基本有序的排序表和数据量不大的排序表。希尔排序正是基于这两点分析对直接插入排序进行改进而得来的，又称缩小增量排序。

希尔排序的基本思想是：先将待排序表分割成若干形如\(L[i,i+d,i+2d,...,i+kd]\)的“特殊”子表,即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ShellSort(ElemType A[],int n){
	//一开始步长为n/2，每次循环，步长减半，最后步长为一时等于直接插入排序。
  for(dk = n / 2; dk >= 1; dk = dk / 2){
    for(i = dk + l; i <= n; ++i) { //等同于一个分组内的直接插入排序
		if(A[i] < A[i - dk]){ //元素值小于其分组前驱 
				A[0] = A[i]; //暂存在A[0]；
				for(j = i - dk; j>0 && A[O] < A[j]; j -= dk) {
					A[j + dk] = A[j]; //记录后移查找插入位置
				}
				A[j + dk] = A[0];//插入
			}//if
		}
	}
}

时间复杂度分析：

由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为\(O(n^{1.3})\)，在最坏情况下希尔排序的时间复杂度为\(O(n^2)\)。

特点：

  1. 希尔排序是一种不稳定的算法。
  2. 希尔排序仅适用于线性表为顺序表的情况。

交换排序

交换排序的思想是根据序列中两个元素关键字的比较结果来对换他们的位置。下面介绍两种常用的交换排序算法，快速排序和冒泡排序。

快速排序

算法思想及描述：

快速排序基于Divide & Conquer，利用递归工作栈，将待排序列不断进行二分。

步骤：

  1. 在待排序列\(L[1...n]\)中，任取一个元素作为枢轴元素pivot（假设取首元素）
  2. 设置low和high指针分别指向数组头尾，low从左向右，high从右向左运动
  3. high指针先进行移动，如发现\(L[high]<pivot\)，则让high指向元素移动到low指向位置，交换运动
  4. 如发现\(L[low]>pivot\)，则让low指向元素移动到high指向位置，交替进行3，4步至low，high指针重合。
  5. 记录上一步low，high指针重合位置以此为划分，分别对两边的子数组进行1，2，3，4步。
快速排序

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Partition(int A[], int low, int high) {
	int pivot = A[low]; //将数组的首元素设置为枢轴
	while(low < high){
		while(low < high && A[high] >= pivot) high--; //找到一个比枢轴元素小的元素
		A[low] = A[high]; //交换位置
		while(low < high && A[low] <= pivot) low++; //找到一个比枢轴元素大的元素
		A[high] = A[low]; //交换位置
	}
	A[low] = pivot; //将枢轴元素放到最终位置
	return low; //返回一趟划分的最终位置
}

void QuickSort(int A[], int low, int high){
	if(low < high) { //递归跳出条件
		int pivotpos = Partition(A, low, high); //划分
		QuickSort(A, low, pivotpos - 1);
		QuickSort(A, pivotpos + 1, high);
	}
}

特点：

  1. 快速排序是不稳定算法，时间复杂度取决于枢轴元素的选取，实质上为划分子树的深度，当递归子树越趋向于平衡二叉树时，时间复杂度\(O(nlog_2{n})\)，当递归子树趋向一边成为单链表时，时间复杂度最高为\(O(n^2)\)，不过通过随机选取使枢轴元素尽可能的为数值中段的元素，可避免最坏情况的发生。递归工作栈深度最大为\(n-1\)，所以空间复杂度为\(O(n)\)。
  2. 数组接近正序或者逆序时，快速排序的效率最低。
  3. 快速排序的每趟划分都会把一个元素放到他的最终位置上！！！

冒泡排序

算法思想及描述：

冒泡排序从前往后（或者从后往前）两两比较相邻元素的值，若为逆序则交换他们的位置，直至序列比较完。这叫第一趟冒泡，下一趟冒泡时，前一趟确认的最小元素不进行比较，每趟冒泡的结果把最小元素（或最大元素）放到了序列的最终位置。最多进行\(n-1\)趟冒泡就能把所有元素排好序。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(int A[], int n) {
  for(i = 0; i < n - 1; i++) {
    flag = false; //标识本趟冒泡是否发生交换
    for(j = n - 1; j > i; j--) { //一趟冒泡过程
      if (A[j - 1] > A[j]) {
        swap(A[j - 1], A[j]);
        flag = true;
      }
    }
    if(flag == false) { //本趟遍历后没有发生交换，说明表已经有序
      return;
    }
  }
}

时间复杂度分析：

当初始序列有序时，显然第一趟冒泡后flag依然为false(本趟冒泡没有元素交换)，从而直接跳出循环，比较次数为\(n-1\)，移动次数为0，从而最好情况下的时间复杂度为 \(O(n)\)。 当初始序列为逆序时，需要进行\(n-1\)趟排序，第i趟排序要进行\(n-i\)次关键字的比较，而且每次比较后都必须移动元素\(n-i\)次来交换元素位置。这种情况下,比较次数=移动次数\(=\sum_{i=1}^{n-1}{(n-i)}=\frac{n(n-1)}{2}\)。

从而，最坏时间复杂度\(O(n^2)\)，平均时间复杂度也为\(O(n^2)\)。

特点：

  1. 冒泡排序是稳定的。
  2. 冒泡排序的每趟划分都会把一个元素放到他的最终位置上！！！

选择排序

选择排序的基本思想是每一趟（如第i趟）在后面\(n-i+1(i=1,2,...,n-1)\)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第\(n-1\)趟做完，待排序元素只剩下1个，就不用再选了。

简单选择排序

伪代码：

1
2
3
4
5
6
7
8
9
10
11
void SelectSort(ElemType A[],int n){
	for(i = 0;i < n - 1;i++){ //一共进行n-1趟
		min = i;	//记录最小元素位置
    for(j = i + l; j < n; j++) {//在A[i...n-1]中选择最小的元素
			if(A[j] < A[min])
        min = j;  //更新最小元素位置
    }
    if(min != i)
      swap(A[i], A[min]);//封装的 swap()函数共移动元素3次
  }
}

时间复杂度分析：

从上述伪码中不难看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过\(3(n-1)\)次，最好的情况是移动0次，此时对应的表已经有序；但元素间比较的次数与序列的初始状态无关，始终是\(\frac{n(n-1)}{2}\)次，因此时间复杂度始终是\(O(n^2)\)。

特点：

  1. 简单选择排序始终无最优情况。

堆排序

算法思想及描述：

首先回忆有关完全二叉树的性质：

  1. 节点i的左孩子---2i， 右孩子---2i+1；
  2. 节点i的父节点---\(\lfloor \frac{i}{2} \rfloor\)；
  3. 节点i的层次---\(\lceil log_{2}(n+1) \rceil\)或者\(\lfloor log_{2}(n) \rfloor+1\)。

堆的定义如下，n个关键字序列\(L[1...n]\)称为堆，当且仅当该序列满足：

  1. \(L[i] \geq L[2i]\) 且 \(L[i] \geq L[2i+1]\) 大根堆 或
  2. \(L[i] \leq L[2i]\)且\(L[i] \leq L[2i+1]\) 小根堆
大根堆示意图

堆排序的思路很简单：首先将存放在\(L[1...n]\)中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例)，堆顶元素就是最大值。 输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。 如此重复，直到堆中仅剩一个元素为止。 输出序列就是一个降序的已排序序列。

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void BuildMaxHeap(ElemType A[],int len){
	for(int i = len / 2; i > 0; i--) //从i=[n/2]~1,反复调整堆
		HeadAdjust(A,i,len);
	}

//函数HeadAdjust将元素k为根的子树进行调整
void HeadAdjust(ElemType A[],int k,int len){
	A[O]=A[k]; //A[0]暂存子树的根结点
	for(i = 2 * k; i <= len;i *= 2){ //沿key较大的子结点向下筛选
		if(i < len && A[i] < A[i + 1])
			i++; //取key较大的子结点的下标
		if(A[0] >= A[i]) {
      break;//筛选结束
    }
		else {
      A[k] = A[i]; //将A[i]调整到双亲结点上
    	k = i;//修改k值,以便继续向下筛选
		}
  }
	A[k] = A[0]; //被筛选结点的值放入最终位置
}

void HeapSort(ElemType A[],int len){
	BuildMaxHeap(A, len);//初始建堆
	for(i = len;i > l;i--) {	//n-1趟的交换和建堆过程
		Swap(A[i], A[1]);	//输出堆顶元素(和堆底元素交换)
		HeadAdjust(A, 1, i-1); //调整,把剩余的i-1个元素整理成堆
	}
}

时间复杂度分析：

建堆时间为\(O(n)\)，之后有\(n-1\)次向下调整操作，每次调整的时间复杂度为\(O(h)\)与树高相关；

建堆\(O(n)+\)向下调整\((n-1)*\)\(O(h)=O(nlog_2n)\)

故在最好、最坏和平均情况下，堆排序的时间复杂度为\(O(nlog_2n)\)。

特点：

  1. 堆排序是一种不稳定的算法。
  2. 堆排序适合关键字较多的情况，取一大堆数中k个最大或者最小数时优先考虑堆排序。

归并排序

写不动了，看心情补充。