常见排序算法详解

常见排序算法详解

常见排序算法的时间复杂度和空间复杂度及稳定性分析：

一、冒泡排序

我们接触的第一个排序算法想必就是冒泡排序了，一般常见的排序算法中最简单的也就是冒泡排序了，它的核心思想在于从前往后开始冒泡，逐一比较两个数的大小。

具体思路：比较相邻元素元素的大小，如果前一个比后一个大，就彼此交换位置，重复以上的步骤，最后将会得到一个升序的数组。

代码示例：

void BubbleSort(vector& v){ int len = v.size(); for (int i = 0; i < len - 1; ++i) for (int j = 0; j < len - 1 - i; ++j) if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);}

冒泡排序优化版

冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说。假如数组原本就是有序，根本不需要排序，它仍然是双层循环一个不少的把数据遍历，这其实就是做了没必要做的事情，属于浪费资源。

针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。

void BubbleSort_orderly(vector& v){ int len = v.size(); bool orderly = false; for (int i = 0; i < len - 1 && !orderly; ++i) { orderly = true; for (int j = 0; j < len - 1 - i; ++j) { if (v[j] > v[j + 1]) { // 从小到大 orderly = false; // 发生交换则仍非有序 swap(v[j], v[j + 1]); } } }}

二、快速排序

要说排序算法中用的最多的就要属快速排序了，它的核心思想也是分治法，分而治之。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后再对左边和右边的两组数分别选出一个基准值，进行同样的比较移动，重复步骤，直到最后都变成单个元素，整个数组就成了有序的序列。

快速排序的思想非常重要，大家一定要理解。此外，快速排序的时间复杂度是O(n log n)，空间复杂度为 O(1)。但这是建立在每次切分都能把数组一刀切两半差不多大的前提下，如果出现极端情况，需要切分 n – 1 次才能完成整个快速排序的过程，这种情况下，时间复杂度就退化成了 O(n^2)，当然极端情况出现的概率也是比较低的。

代码示例：

void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r);}

三、归并排序

归并算法的核心思想也是分治法，就是将一个数组一刀切两半，递归切，直到切成单个元素，然后重新组装合并，单个元素合并成小数组，两个小数组合并成大数组，直到最终合并完成，排序完毕。

具体思路：把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。归并排序的核心思想是分治，分而治之，将一个大问题分解成无数的小问题进行处理，处理之后再合并，这里我们采用递归来实现：

void merge_sort(int q[], int l, int r){ if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int k = 0, i = l, j = mid + 1; while (i <= mid && j <= r) if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ]; else tmp[k ++ ] = q[j ++ ]; while (i <= mid) tmp[k ++ ] = q[i ++ ]; while (j <= r) tmp[k ++ ] = q[j ++ ]; for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];}

四、堆排序

堆是是一棵完全二叉树，堆上面的每个节点满足父节点的值大于子节点。若根节点的值比所有节点的值都大， 称为最大堆；根节点的值比所有节点的值都小， 称为最小堆；

具体思路：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1和序列重新构造成一个堆，这也就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。

// 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。void max_heapify(int arr[], int start, int end){ int dad = start; int son = dad * 2 + 1; while (son <= end) { if (son + 1 <= end && arr[son] < arr[son + 1]) son++; if (arr[dad] > arr[son]) return; else { swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }} void heap_sort(int arr[], int len){ for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }}

五、桶排序

桶排序将要排的数据分到多个有序的桶里，每个桶里的数据再单独排序，再把每个桶的数据依次取出，即可完成排序。

具体思路：先设置一个定量的数组当作空桶子；寻访序列，并且把项目一个一个放到对应的桶子去；对每个不是空的桶子进行排序；从不是空的桶子里把项目再放回原来的序列中。

代码示例：

void insert_sort(vector& arr){ int n = arr.size(); int j = 0, cur = 0; for (int i = 1; i < n; i++) { cur = arr[i]; j = i - 1; //进行比较，插入 while (j >= 0 && arr[j] > cur) { arr[j + 1] = arr[j]; j--; } arr[j+1] = cur; }}void bucket_sort(vector& arr){ if (arr.size() == 0) return; int minvalue = arr[0]; int maxvalue = arr[0]; for (int i = 1; i < arr.size(); i++) { if (arr[i] < minvalue) { minvalue = arr[i]; // 输入数据的最小值 } else if (arr[i] > maxvalue) { maxvalue = arr[i]; // 输入数据的最大值 } } //桶进行初始化 int DEFAULT_BUCKET_SIZE = 5; // 桶的大小的默认为5 int bucketCount = (maxvalue - minvalue) / DEFAULT_BUCKET_SIZE + 1; //计算桶的数量 vector> buckets(bucketCount, vector()); // 利用映射函数将数据分配到各个桶中 for (int i = 0; i < arr.size(); i++) { buckets[(arr[i] - minvalue) / DEFAULT_BUCKET_SIZE].push_back(arr[i]); } int index = 0; for (int i = 0; i < buckets.size(); i++) { insert_sort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序 for (int j = 0; j < buckets[i].size(); j++) { arr[index++] = buckets[i][j]; } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。