经典排序算法整理

发布 : 2020-09-17 分类 : 算法 浏览 :

经典排序算法

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

冒泡排序

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


冒泡排序的思想如下:

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


效果如下:
1.gif


示例代码:

1
2
3
4
5
6
7
8
9
10
11
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)$ 数组不稳定、链表稳定


选择排序思想如下:

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


效果如下:
2.gif


示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
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


效果如下:
3.gif


示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
}
}
}
本文作者 : HeoLis
原文链接 : http://ishero.net/%E7%BB%8F%E5%85%B8%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%95%B4%E7%90%86.html
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

学习、记录、分享、获得

微信扫一扫, 向我投食

微信扫一扫, 向我投食