经典排序算法整理

经典排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 快速排序
• 堆排序
• 归并排序
• 希尔排序
• 计数排序
• 桶排序
• 基数排序

冒泡排序

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定

冒泡排序的思想如下：

• 从首位开始，比较相邻两元素的大小，若第一个元素比第二个大，则交换他们。（每次将最大的移到末尾）
• 重复以上步骤，直到没有任何一对数字需要比较。

效果如下：

示例代码：

void bubbleSort(int arr[], int n){	// 待排序数组，数组长度
	for (int i = 0; i < n - 1; i++){
		for (int j = 0; j < n - i - 1; j++){
			if (arr[j] > arr[j+1]){
				int tmp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = tmp;
			}
		}
	}
}

选择排序

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	数组不稳定、链表稳定

选择排序思想如下：

• 首先从未排序序列中找到最小或最大元素，放到排序序列的起始位置。
• 从剩余未排序元素中继续寻找最小或做大元素，然后放到已排序序列的末尾
• 重复以上过程，直到完成排序

效果如下：

示例代码：

void selectionSort(int arr[], int n){	// 待排序数组，数组长度
	for (int i = 0; i < n; i++){
		int minIdx = i;
		for (int j = i; j < n; j++){
			if (arr[j] <arr[minIdx]){
				minIdx = j;
			}
		}
		int tmp = arr[i];
		arr[i] = arr[minIdx];
		arr[minIdx] = tmp;
	}
}

插入排序

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	数据对象稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定

插入排序算法思想：

• 1.从第一个元素开始，该元素可以认为已经被排序
• 2.取出下一个元素，在已经排序的元素序列中从后向前扫描
• 3.如果该元素（已排序）大于新元素，将该元素移到下一位置
• 4.重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
• 5.将新元素插入到该位置后
• 6.重复步骤 2~5

效果如下：

示例代码：

void insertSort(int arr[], int n) {
	for (int i = 1; i < n; i++){
		if (arr[i] < arr[i-1]){
			int j = i - 1;	// 有序序列尾部下标
			int tmp = arr[i];
			arr[i] = arr[i-1];
			while (tmp < arr[j]){	// 后移
				arr[j+1] = arr[j];
				j--;
			}
			arr[j+1] = tmp;	// 加1弥补循环最后的减1
		}
	}
}