计数排序 计数排序是一种稳定的线性时间排序算法,计数排序不是比较排序,排序的速度快于任何比较排序算法,计数排序可以配合基数排序,能够更有效排序数据范围很大的数组 一、计数排序步骤 1.找出待排序的数组中最大和最小的元素 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项 3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加) 4.反向填充目标数组:将每个元素i放在新数组的第C(i)项, 2022-03-03 数据结构和算法 算法 排序 笔记 非比较排序
基数排序 基数排序是将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,一次进行一次排序。这样从最低位排序一直到最高位排序完成之后,数列就变成一个有序序列 NOTE: 基数排序只能排序非负整数 一、效率基数排序的时间复杂度为 O(k*n)其中n是排序元素个数,k是数字位数。需要注意的是这个时间复杂度不一定优于 O(n*log_n) 二、实现基数排序的过程图示如下: 2022-03-03 数据结构和算法 算法 排序 笔记 非比较排序
希尔排序 12345678910111213141516171819202122232425void shell(vector<int>& nums){ int size = nums.size(); int h = 1; while (h < (size / 3)) { h = 3 * h + 1;  2022-03-03 数据结构和算法 算法 排序 笔记 比较排序
归并排序 一、经典归并排序归并排序就是将要排序的数组分成两部分,每一部分都排好序,再将这两部分归并为一个数组,每一部分的排序又采用归并排序。 归并排序按照空间的使用上来分主要分为两种:普通归并和原地归并。按照归并的方向可以分为自顶向下归并和自底向上归并。 1. merge函数归并排序最主要的一个函数就是merge,函数接口如下: 1void merge(int data[], int start, int 2022-03-03 数据结构和算法 算法 排序 笔记 比较排序
堆排序 一、堆结构1. 堆的定义堆中某个节点的值总是大于等于其子节点的值,并且堆是一颗完全二叉树。 堆可以用数组来表示,这是因为堆是完全二叉树,而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2,而它的两个子节点的位置分别为 2k 和 2k+1。 这里不使用数组索引为 0 的位置,是为了更清晰地描述节点的位置关系。 1234int heap[maxN+1];int N = 2022-03-03 数据结构和算法 算法 排序 笔记 比较排序
选择排序 一、简单选择排序选择排序每次遍历数组时,从数组中未排序部分中选择出最大(最小)元素,并将该元素与未排序部分的最后一个(第一个)元素交换,最后得到有序数组 1234567891011121314151617void selection(vector<int>& nums){ int min_i = 0; int size = nums.size(); 2022-03-03 数据结构和算法 算法 排序 笔记 比较排序
插入排序 一、简单插入排序插入排序将数组分为排序区和乱序区,排序过程中每次从乱序区中选择一个元素放入排序区,直到乱序区没有元素 1234567891011void insertion(vector<int>& nums){ int size = nums.size(); for (int i = 1; i < size; i++) { 2022-03-03 数据结构和算法 算法 排序 笔记 比较排序
冒泡排序 冒泡排序是最基本的排序方式,是在每次遍历时,通过交换相邻元素将未排序元素中最大元素(最小元素)沉下去(浮上来)的过程。 一、经典的冒泡排序:123456789101112131415void bubble(vector<int>& nums){ int size = nums.size(); //外层循环:每次循环排序好一个元素 for (int i 2022-03-03 数据结构和算法 算法 排序 笔记 比较排序