程序员人生 网站导航

常用的七大排序算法

栏目:php教程时间:2015-03-05 08:37:10

1:冒泡排序:

// BubbleSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> 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⑴] > a[j]) { Swap(a[j⑴],a[j]); } } } } void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } 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<<"排序前:"<<endl; PrintNum(a,Num); BubbleSort(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }


2:直接插入排序:

// InsertSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* 插入排序是稳定排序 插入排序:O(n^2); */ void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } void InsertSort(int a[], int n) { int i,j; for ( i = 1; i < n; i++)//从1开始 a[0] 自动默许为有序 { if (a[i] < a[i⑴]) { int temp = a[i]; for (j = i⑴; j>=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⑴]) { int temp = a[i]; for (j= i ⑴;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<<"排序前:"<<endl; PrintNum(a,Num); InsertSort2(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }


3:希尔排序:

// ShellSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* 希尔排序: 1:希尔排序的本质是分组直接插入排序; 2:把记录按下标的1定增量分组,对每组使用直接插入排序算法排序;随着增量逐步减少,每组包括的关键词愈来愈多, 当增量减至1时,全部文件恰被分成1组,算法便终止。 3:希尔排序不是稳定的排序 4:希尔排序的时间复杂度: 比O(n^2)略微好1点 5:希尔排序是依照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少, 速度很快;当元素基本有序了,步长很小,插入排序对有序的序列效力很高。所以,希尔排序的时间复杂度会比o(n^2) 好1些。 */ void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } void ShellSort(int a[], int n) { int i; int gap; for(gap = n/2; gap>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<<"排序前:"<<endl; PrintNum(a,Num); ShellSort(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }

4:选择排序:

// SelectSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* 直接选择排序和直接插入排序类似,都将数据分为有序区和无序区,所不同的是直接插入排序 是将无序区的第1个元素直接插入到有序区以构成1个更大的有序区,而直接选择排序是从无序区 选1个最小的元素直接放到了有序区的最后 数组 a[0...n⑴] 1:初始时,数组全为无序区为 a[0...n⑴].令i=0; 2:在无序区a[i...n⑴]当选取1个最小的元素,将其与a[i]交换。交换以后a[0...i]就构成了1个有序区 3:i++并重复第2步知道 i == n⑴.排序完成 选择排序不是稳定排序 例如有: 5 8 5 2 9 第1次排序后 第1个 5与2 交换,那末两个5的相对位置产生了变化。 时间复杂度也是O(n^2)不过比冒泡排序整体来讲好1点 */ void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } void Swap(int& a, int& b) { int temp = a; a = b; b = temp; } void SelectSort(int a[], int n) { int i,j,nMin; for (int i = 0; i < n; i++) { nMin = i; for (int j = i+1; j < n; j++) { if (a[j] < a[nMin]) { nMin = j; } } Swap(a[nMin],a[i]); } } 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<<"排序前:"<<endl; PrintNum(a,Num); SelectSort(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }


5:归并排序:

// MergeSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* 归并排序: 时间复杂度: O(NlogN) 是稳定的排序 归并排序是建立在归并操作上的1种有效的排序算法,该算法是采取分治法(Divide and Conquer)的1个非常典型的利用。 将已有序的子序列合并,得到完全有序的序列;即先使每一个子序列有序,再使子序列段间有序。若将两个有序表合并成1个 有序表,称为2路归并。 归并进程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第1个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1; 否则将第2个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中1个有序表取完,然后再将 另外一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通经常使用递归实现,先把待排序区间[s,t] 以中点2分,接着把左侧子区间排序,再把右侧子区间排序,最后把左区间和右区间用1次归并操作合并成有序的区间[s,t]。 */ void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } void mergeArray(int a[], int first, int mid, int last, int temp[]) { int i = first; int j = mid+1; int m = mid; int n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } while (i<=m) { temp[k++] = a[i++]; } while (j<=n) { temp[k++] = a[j++]; } for ( i = 0; i < k; i++) { a[first+i] = temp[i]; } } void mergeSort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first+last)/2; mergeSort(a,first,mid,temp);//左侧排序 mergeSort(a,mid+1,last,temp);//右侧排序 mergeArray(a,first,mid,last,temp);//合并两个有序数列 } } bool MergeSort(int a[], int n) { int *p = new int[n]; mergeSort(a,0,n⑴,p); delete[] p; return true; } 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<<"排序前:"<<endl; PrintNum(a,Num); MergeSort(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }


6:快速排序:

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


7:堆排序:

// HeapSort.cpp : 定义控制台利用程序的入口点。 // #include "stdafx.h" #include <iostream> using namespace std; /* 不稳定:就是大小相同的两个数,经过排序后,终究位置与初始位置交换了。 快速排序:27 23 27 3以第1个27作为pivot中心点,则27与后面那个3交换,构成3 23 27 27, 排序经过1次结束,但最后那个27在排序之初先于初始位置3那个27,所以不稳定。 堆排序:比如:3 27 36 27,如果堆顶3先输出,则,第3层的27(最后1个27)跑到堆顶, 然后堆稳定,继续输出堆顶,是刚才那个27,这样说明后面的27先于第2个位置的27输出,不稳定。 */ void PrintNum(int a[],int n) { for (int i = 0; i < n; i++) { cout<<a[i]<<" "; } } void HeapAdjust(int a[], int start, int end) { int temp = a[start]; for (int i = 2*start + 1; i <= end ; i*=2) { if (i<end && a[i]<a[i+1])//左右孩子比较 { ++i;//如果左孩子的值小于右孩子的值,则++i, i为较大的记录的下标 } else { //i不做处理 } if (temp > a[i]) //左右孩子中获胜者与父亲的比较 { break;//如果左右孩子中最大的都比父节点的值小,则不需要做处理 } else { //将孩子节点进行上位,则以孩子节点的位置进行下1轮的挑选 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⑴; i > 0 ; --i) { //最后1个元素和第1元素进行交换 int temp = a[i]; a[i] = a[0]; a[0] = temp; //然后将剩下的无序元素继续调剂为大顶堆 HeapAdjust(a,0,i⑴); } } 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<<"排序前:"<<endl; PrintNum(a,Num); HeapSort(a,Num); cout<<endl<<"排序后:"<<endl; PrintNum(a,Num); getchar(); return 0; }



 

------分隔线----------------------------
------分隔线----------------------------

最新技术推荐