【排序】八大排序算法简介及它们各自的特点总结 |
您所在的位置：网站首页 › 复杂数据结构的特点 › 【排序】八大排序算法简介及它们各自的特点总结 |
【排序】八大排序算法简介及它们各自的特点总结
|
概述：
一般使用的八大排序算法是：插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、堆排序、基数排序，每个方法有其适合的使用场景，可以根据具体数据进行选择. 几个概念： 内部排序：排序期间元素全部存放在内存中的排序； 外部排序：排序期间元素无法全部存放在内存中，必须在排序过程中根据要求不断地进行内外存之间移动地排序； (这八种排序算法中除了多路归并排序是外部排序，其他都是内部排序) 稳定性：指的是经过排序后，值相同的元素保持原来顺序中的相对位置不变. 各算法时间复杂度、空间复杂度、所需辅助空间与稳定性如下：
实现方法(这里都是进行从小到大的排序)： 1.冒泡排序： 冒泡排序思想很简单，就是对每个下标i，取j从0到n-1-i(n是数组长度)进行遍历，如果两个相邻的元素s[j]>s[j+1]，就交换，这样每次最大的元素已经移动到了后面正确的位置. void bubbleSort(vector &s){ for (int i = 0; i < s.size(); i++){ for (int j = 0; j < s.size() - 1 - i; j++){ if (s[j] > s[j + 1]) swap(s[j], s[j + 1]); } } }冒泡排序的特点：稳定，每次排序后，后面的元素肯定是已经排好序的，所以每次排序后可以确定一个元素在其最终的位置上，冒泡排序比较次数：n(n-1)/2，移动次数：3n(n-1)/2. 2.插入排序：插入排序又分为简单插入排序和折半插入排序；简单插入排序思想是每趟排序把元素插入到已排好序的数组中，折半插入排序是改进的插入排序，由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度. 简单插入排序： void insertSort(vector &s){ if (s.size() > 1){ for (int i = 1; i < s.size(); i++){ for (int j = i; j > 0 && s[j] < s[j - 1]; j--){ swap(s[j], s[j - 1]); } } } }折半插入排序： void binaryInsertSort(vector &s){ int low, high, m, temp, i, j; for (i = 1; i < s.size(); i++){ //采用折半查找方法，寻找应该插入的位置 low = 0; high = i - 1; while (low s[i]) high = m - 1; else low = m + 1; } //统一移动元素，将该元素插入到正确的位置 temp = s[i]; for (j = i; j > high + 1; j--){ s[j] = s[j - 1]; } s[high + 1] = temp; } }插入排序的特点： 1.稳定; 2.最坏情况下比较n*(n-1)/2次，最好情况下比较n-1次; 3.第k次排序后，前k个元素已经是从小到大排好序的 3.简单选择排序：选择排序思想是对每个下标i,从i后面的元素中选择最小的那个和s[i]交换. void selectSort(vector &s){ if(s.size()>1){ for(int i=0;i |
【本文地址】