锐客网

  1. 首页 > it技术 > >

常用的七大排序算法

c

1：冒泡排序：

// BubbleSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*冒泡排序是稳定排序时间复杂度是 O(n^2)*/void Swap(int& a, int& b){ int temp = a; a=b; b=temp; }void BubbleSort(int a[], int n){ int i, j; for (i = 0; i < n; i++) {for (j = 1; j < n-i; j++){if (a[j-1] > a[j]){Swap(a[j-1],a[j]); }} }}void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout<


2：直接插入排序：
// InsertSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*插入排序是稳定排序插入排序：O(n^2); */void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout<=0 && a[j] > temp; j--){a[j+1] = a[j]; }a[j+1] = temp; //当遇到a[j] < temp的时候，a[j+1]赋值为temp} }}void InsertSort2(int a[], int n){ int i,j; for(i = 1; i < n; i++) {if (a[i] < a[i-1]){int temp = a[i]; for (j= i -1; j>=0 && a[j] > temp; j--){a[j+1] = a[j]; }a[j+1] = temp; } }}int _tmain(int argc, _TCHAR* argv[]){ int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55}; int Num = sizeof(a)/sizeof(a[0]); cout<<"排序前："<


3：希尔排序：
// ShellSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*希尔排序：1：希尔排序的本质是分组直接插入排序；2：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。3：希尔排序不是稳定的排序4：希尔排序的时间复杂度：比O(n^2)稍微好一点 5：希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。*/void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout<0; gap /= 2) {for ( i = gap; i < n; i++){if (a[i] < a[i-gap]){int temp = a[i]; int j; for ( j = i-gap; j>=0 && a[j] > temp; j -= gap){a[j+gap] = a[j]; }a[j+gap] = temp; }} }}int _tmain(int argc, _TCHAR* argv[]){ int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55}; int Num = sizeof(a)/sizeof(a[0]); cout<<"排序前："<

4：选择排序：
// SelectSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到了有序区的最后数组 a[0...n-1]1:初始时，数组全为无序区为 a[0...n-1].令i=0; 2:在无序区a[i...n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0...i]就形成了一个有序区3：i++并重复第二步知道 i == n-1.排序完成选择排序不是稳定排序例如有： 5 8 5 2 9 第一次排序后 第一个 5与2 交换，那么两个5的相对位置发生了变化。时间复杂度也是O(n^2)不过比冒泡排序总体来说好一点*/void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout<

【常用的七大排序算法】
5：归并排序：
// MergeSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*归并排序：时间复杂度： O(NlogN)是稳定的排序归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。 */void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout<


6：快速排序：
// QuickSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*快速排序的排序效率在同为O(NLogN)的几种排序方法中效率较高快速排序的思路： 挖坑填数+分治法1：先从数组当中取一个数作为基准数例如 a[0]2: 分区过程，将比这个数大的数全部放到它的右边，小于或等于它的数全部放到它的左边3：再对左右区间重复第二步，直到各区间只要一个数快速排序不是稳定的排序，这也是它与归并排序相比最大的缺点eg：3 2 4 5 6 2 7第一步 从右往做找到比a[0]小的数字2，2填充到3 的位置，那么两个2 的相对位置发生了变化，所以不是稳定的排序*/void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout< end) {return; } int i = start; int j = end; int k = a[i]; //a[i]是第一个坑 while (i < j) {//从右往左找小于k的数来填 a[i]while (i < j && a[j] >= k){j--; }if (i < j){a[i] = a[j]; //将a[j]填到a[i]中，a[j]就是新的一个坑}//从左往右找大于k的数来填 a[j]while (i < j && a[i] < k){i++; }if (i < j){a[j] = a[i]; //将a[i]填到a[j]中，a[i]又是新的一个坑} } //退出时，i=j，将k填到这个坑当中 a[i] = k; QuickSort(a,i+1,end); QuickSort(a,start,i-1); }int _tmain(int argc, _TCHAR* argv[]){ int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55}; int Num = sizeof(a)/sizeof(a[0]); cout<<"排序前："<


7：堆排序：
// HeapSort.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include using namespace std; /*不稳定：就是大小相同的两个数，经过排序后，最终位置与初始位置交换了。快速排序：27 23 27 3以第一个27作为pivot中心点，则27与后面那个3交换，形成3 23 27 27，排序经过一次结束，但最后那个27在排序之初先于初始位置3那个27，所以不稳定。堆排序：比如：3 27 36 27，如果堆顶3先输出，则，第三层的27（最后一个27）跑到堆顶，然后堆稳定，继续输出堆顶，是刚才那个27，这样说明后面的27先于第二个位置的27输出，不稳定。*/void PrintNum(int a[],int n){ for (int i = 0; i < n; i++) {cout< a[i]) //左右孩子中获胜者与父亲的比较{break; //如果左右孩子中最大的都比父节点的值小，则不需要做处理}else{//将孩子节点进行上位，则以孩子节点的位置进行下一轮的筛选a[start] = a[i]; start = i; } } a[start] = temp; }void HeapSort(int a[], int n){ //先建立大顶堆 for (int i = n/2; i >=0; --i) {HeapAdjust(a,i,n); } //进行排序 for (int i = n-1; i > 0 ; --i) {//最后一个元素和第一元素进行交换int temp = a[i]; a[i] = a[0]; a[0] = temp; //然后将剩下的无序元素继续调整为大顶堆HeapAdjust(a,0,i-1); }}int _tmain(int argc, _TCHAR* argv[]){ int a[] = {2,4,3,6,5,1,7,8,9,33,2,4,55}; int Num = sizeof(a)/sizeof(a[0]); cout<<"排序前："<




    推荐阅读


    上一篇：Java高级|原子变量、无锁算法和非阻塞机制

    下一篇：算法|寻找峰值-162-[中等]- [二分查找模板 - II ]