排序:
1、排序在计算机数据处理中经常遇到,在日常的数据处理中,一般可以认为有 1/4 的时间用在排序上,而对于程序安装,
多达 50% 的时间花费在对表的排序上。简而言之,排序是将一组杂乱无章的数据按一定的规律顺次排列起来
2、内排与外排:根据排序方法在排序过程中数据元素是否完全在内存而划分,若一部分数据在外存,则为外排,否则,为内排
3、排序算法的稳定性:根据排序后相同元素顺序是否会发生改变而定,
如两个数 a 与 b,a == b 且 a 在 b 的前面,若排序后 a 仍然在 b 的前面,则为稳定的,否则,为不稳定的
4、排序算法的性能评估:算法的执行时间是衡量算法好坏的最重要参数,其时间开销可用算法执行中的数据比较次数与移动次数来衡量
排序算法:
1、时间复杂度:
a、平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序
b、线性对数阶 (O(nlog2n)) 排序:快速排序、堆排序和归并排序
c、O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数:希尔排序
d、线性阶 (O(n)) 排序:基数排序,桶排序和计数排序
2、稳定性:
a、稳定的排序算法:冒泡排序、插入排序、归并排序、计数排序、桶排序和基数排序
b、不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序
注:稳定性是相对的,例如我们把比较冒泡排序里对两个元素比较的算法改成大于等于,它会变成不稳定的!
3、比较与非比较:
a、比较排序:冒泡排序、插入排序、希尔排序、选择排序、快速排序、归并排序和堆排序
b、非比较排序:计数排序、桶排序和基数排序
十大经典排序算法:
以下均按非降序排序
1、冒泡排序(bubbleSort):
a、比较相邻两个元素,若前者的大于后者,则交换这两个元素
b、向后移动一项,再执行比较交换操作;当移动到最后一位时,这个元素即为本轮最大值
c、从新从头开始,除了最后一项,执行 a、b 操作,直到排序完成
注:在排序过程中,我们可以设置一个标志判断在一轮排序中是否有交换元素,若一轮排序过后仍无交换,则说明排序已完成
#include #include #include //采用引用的方式传参,否则传入的只是一个不会改变原数据的形参 void bubbleSort(std::vector & nums);int main(){ std::vector nums; int len = 0; std::cout<<"请输入长度:"; do { std::cin>>len; if (len <= 0)// 标准错误流,输出错误信息 std::cerr<<"请输入正整数:"; } while (len <= 0); int num = 0; std::cout<<"输入 "< <<" 个数: ";// size_t 是 unsigned_int 类型,建议在使用下标时使用,但若将负数赋值给它,则会将该数转换为正数,从而产生错误 for (size_t i = 0; i < len; ++i) { std::cin>>num; nums.push_back(num); } bubbleSort(nums); std::cout<<"排序后的数组:";// 自由 for 循环 for (int num : nums)// std::ends 输出空白符,不同电脑的空白符可能不一样 std::cout< <
& nums){// 设置交换标志,若一次循环后所有元素都未发生交换,则说明数组已经排列好,可提前退出 bool exchange = false; size_t len = nums.size(); for (size_t i = 1; i < len; ++i) { exchange = false;// 为了方便,我把最小的元素移动到了最前 for (size_t j = len-1; j >= i; j--) { if (nums[j-1] > nums[j]) { int temp = nums[j-1]; nums[j-1] = nums[j]; nums[j] = temp; exchange = true; } } if (!exchange) return; }}
View Code void selectionSort(std::vector & nums){ size_t len = nums.size();// 在每次循环里选出最小的一个排在前面 for (size_t i = 0; i < len-1; ++i){ int min = i; for (size_t j = i+1; j < len; ++j){ if (nums[j] < nums[min]) min = j; } if (i != min){ int temp = nums[i]; nums[i] = nums[min]; nums[min] = temp; } } return ;}
View Code void insertionSort(std::vector & nums){ size_t len = nums.size(); for (size_t i = 1; i < len; i++) { int temp = nums[i]; // 在循环中把较大的数往后移一位 size_t j = i; while (j > 0 && temp < nums[j-1]) { nums[j] = nums[j-1]; j--; } if (j != i) nums[j] = temp; } return ;}
View Code void shellSort(std::vector & nums){ int gap = 1, len = nums.size();// 先让间隔 gap 尽量大 while (gap < len) gap = gap*3+1; while (gap > 0){ for (int i = gap; i < len; i++){ int temp = nums[i]; int j = i - gap;// 直接插入排序 while (j >= 0 && nums[j] > temp){ nums[j+gap] = nums[j]; j -= gap; } nums[j+gap] = temp; } gap /= 3; } return ;}
View Code void QuickSort(int* arr, int low, int high){ int star = low, end = high; if (star > end) return ; int temp = arr[star]; while (star != end) {// 从后找出小于“基准”的数 while (arr[end] >= temp && star < end) end--;// 从前找出大于“基准”的数 while (arr[star] <= temp && star < end) star++;// 若还在范围内,则交换这两者 if (star < end) { int t = arr[star]; arr[star] = arr[end]; arr[end] = t; } }// 把“基准”移动到“中间” int t = arr[low]; arr[low] = arr[star]; arr[star] = t; // 递归 QuickSort(arr, low, star-1); QuickSort(arr, star+1, high); return ;}
View Code