首页 > 代码库 > 经典排序算法总结（代码） .（转）
经典排序算法总结（代码） .（转）
经典排序算法总结（代码）
·冒泡法
·快速排序
·插入排序
·希尔（shell）排序
·选择排序
·堆排序
·归并排序
附：
排序算法原理：http://zh.wikipedia.org/wiki/Category:%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
flash演示:http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/list.asp?id=7
归并排序的具体介绍在下面的文章里：
递归算法学习---归并排序
[cpp] view plaincopyprint?#include <iostream> #include <string> using namespace std; /* 冒泡法 左右元素相比，往后冒泡 */ template<typename T> void BubbleSort(T* r, int n) { T temp; int i,j; for (i=0;i<n-1;i++) { for (j=0;j<n-i-1;j++) { if (r[j] > r[j+1]) { temp = r[j]; r[j] = r[j+1]; r[j+1] = temp; } } } } #include <iostream>#include <string>using namespace std; /* 冒泡法 左右元素相比，往后冒泡 */template<typename T>void BubbleSort(T* r, int n){ T temp; int i,j; for (i=0;i<n-1;i++) { for (j=0;j<n-i-1;j++) { if (r[j] > r[j+1]) { temp = r[j]; r[j] = r[j+1]; r[j+1] = temp; } } }} [cpp] view plaincopyprint?/*快速排序 左边比他小，右边比他大，每次得到一个最左边数据的位置*/ template<typename T> void QuickSort(T a[],int low,int high) { if(low < high) { T elem = a[low]; int l = low, r = high; while(l < r) { while(l < r && a[r] >= elem) r--; if (l < r) { a[l++] = a[r]; } while(l< r && a[l] <= elem) l++; if (l < r) { a[r--] = a[l]; } } a[r] = elem; QuickSort(a,low,r-1); QuickSort(a,r+1,high); } } /*快速排序左边比他小，右边比他大，每次得到一个最左边数据的位置*/template<typename T>void QuickSort(T a[],int low,int high){ if(low < high) { T elem = a[low]; int l = low, r = high; while(l < r) { while(l < r && a[r] >= elem) r--; if (l < r) { a[l++] = a[r]; } while(l< r && a[l] <= elem) l++; if (l < r) { a[r--] = a[l]; } } a[r] = elem; QuickSort(a,low,r-1); QuickSort(a,r+1,high); }}[cpp] view plaincopyprint?/*插入排序 向右移，a[j+1]=a[j]*/ template<typename T> void insert_sort(T a[],int n) { int i,j; T elem; for (i= 1;i<n ;++i) { j = i- 1; elem = a[i]; while(j>=0&& elem < a[j] ) { a[j+1] = a[j]; j--; } a[j+1] = elem; } } /*插入排序向右移，a[j+1]=a[j]*/template<typename T>void insert_sort(T a[],int n){ int i,j; T elem; for (i= 1;i<n ;++i) { j = i- 1; elem = a[i]; while(j>=0&& elem < a[j] ) { a[j+1] = a[j]; j--; } a[j+1] = elem; } } [cpp] view plaincopyprint?/*希尔（shell）排序 把插入排序的改成d即可*/ template<typename T> void shell_insert(T array[],int d,int len) { int i,j; T elem; for ( i = d;i < len;i++) { j = i - d; elem = array[i]; while (j >= 0&& elem < array[j]) { array[j+d] = array[j]; j = j - d; } array[j+d] = elem; } } template<typename T> void shell_sort(T array[],int len) { int inc = len; do { inc = inc/2; shell_insert(array,inc,len); } while (inc >1); } /*希尔（shell）排序把插入排序的改成d即可*/template<typename T>void shell_insert(T array[],int d,int len){ int i,j; T elem; for ( i = d;i < len;i++) { j = i - d; elem = array[i]; while (j >= 0&& elem < array[j]) { array[j+d] = array[j]; j = j - d; } array[j+d] = elem; }} template<typename T>void shell_sort(T array[],int len){ int inc = len; do { inc = inc/2; shell_insert(array,inc,len); } while (inc >1);} [cpp] view plaincopyprint?/*选择排序 逐一比较，最小的放前面*/ template <typename T> void SelectSort(T a[],int n) { int i,j,elemNum; T elem; for (i=0;i<n-1;i++) { elemNum = i; for (j= i+1;j<n;j++) { if (a[j] < a[elemNum]) { elemNum = j; } } if (elemNum != i) { elem = a[i]; a[i] = a[elemNum]; a[elemNum] = elem; } } } /*选择排序逐一比较，最小的放前面*/template <typename T>void SelectSort(T a[],int n){ int i,j,elemNum; T elem; for (i=0;i<n-1;i++) { elemNum = i; for (j= i+1;j<n;j++) { if (a[j] < a[elemNum]) { elemNum = j; } } if (elemNum != i) { elem = a[i]; a[i] = a[elemNum]; a[elemNum] = elem; } }}[cpp] view plaincopyprint?/*堆排序 a[s]>=a[2*s] &&a[s]>=a[2*s+1]*/ template<typename T> void Max_heap(T a[],int S,int len) { int l = 2*S; int r = 2*S+1; int maxI = S; T elem; if (l < len && a[l] > a[maxI]) { maxI = l; } if (r < len && a[r] > a[maxI]) { maxI = r; } if (maxI != S) { elem = a[S]; a[S] = a[maxI]; a[maxI] = elem; Max_heap(a,maxI,len); } } template<typename T> void HeapSort(T a[],int n) { int i; T elem; for (i = n/2;i>=0;i--) { Max_heap(a,i,n); } for (i= n-1;i>=1;i--) { elem = a[0]; a[0] = a[i]; a[i] = elem; n = n-1; Max_heap(a,0,n); } } /*堆排序a[s]>=a[2*s] &&a[s]>=a[2*s+1]*/template<typename T>void Max_heap(T a[],int S,int len){ int l = 2*S; int r = 2*S+1; int maxI = S; T elem; if (l < len && a[l] > a[maxI]) { maxI = l; } if (r < len && a[r] > a[maxI]) { maxI = r; } if (maxI != S) { elem = a[S]; a[S] = a[maxI]; a[maxI] = elem; Max_heap(a,maxI,len); }} template<typename T>void HeapSort(T a[],int n){ int i; T elem; for (i = n/2;i>=0;i--) { Max_heap(a,i,n); } for (i= n-1;i>=1;i--) { elem = a[0]; a[0] = a[i]; a[i] = elem; n = n-1; Max_heap(a,0,n); }}[cpp] view plaincopyprint?/*归并排序 左边小左边，左边++；右边小取右边，右边++*/ template<typename T> void merge(T array[], int low, int mid, int high) { int k; T *temp = new T[high-low+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 int begin1 = low; int end1 = mid; int begin2 = mid + 1; int end2 = high; for (k = 0; begin1 <= end1&& begin2 <= end2; ++k) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 { if(array[begin1]<=array[begin2]) temp[k] = array[begin1++]; else temp[k] = array[begin2++]; } if(begin1 <= end1) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾 memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(T)); if(begin2 <= end2) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾 memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(T)); memcpy(array+low, temp, (high-low+1)*sizeof(T));//将排序好的序列拷贝回数组中 delete temp; } template<typename T> void merge_sort(T array[], unsigned int first, unsigned int last) { int mid = 0; if(first<last) { //mid = (first+last)/2; /*注意防止溢出*/ mid = first/2 +last/2; //mid = (first & last) + ((first ^ last) >> 1); merge_sort(array, first, mid); merge_sort(array, mid+1,last); merge(array,first,mid,last); } } template<typename T> void Print(T* r,int n) { for (int i=0;i<n;i++) { cout << r[i] << endl; } } int main() { cout << "Welcome..."<< endl; double r[] ={1.5,3.2,5,6,9.2,7,2,4,8}; //BubbleSort(r,9); QuickSort(r,0,8); //insert_sort(r,9); //shell_sort(r,9); //SelectSort(r,9); //HeapSort(r,9); // merge_sort(r,0,8); Print(r,9); return 0; }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。