一.歸并排序

#include<iostream> using namespace std; void Merge(int arr[],int low,int mid,int high); void MergeSort (int arr [], int low,int high) {if(low>=high) return; int mid = low + (high - low)/2; MergeSort(arr,low,mid); MergeSort(arr,mid+1,high); Merge(arr,low,mid,high); } void Merge(int arr[],int low,int mid,int high){int i=low,j=mid+1,k=0; int *temp=new int[high-low+1];while(i<=mid&&j<=high){if(arr[i]<=arr[j]) temp[k++]=arr[i++];elsetemp[k++]=arr[j++];}while(i<=mid)temp[k++]=arr[i++];while(j<=high)temp[k++]=arr[j++];for(i=low,k=0;i<=high;i++,k++)arr[i]=temp[k];delete []temp; } int main(){int n;cin>>n;int* a=new int[n];int cnt=0;while(cnt<n){cin>>a[cnt++];}MergeSort(a,0,n-1);for(int i=0;i<n;i++){cout<<a[i]<<" ";}delete []a;return 0; }

二.快速排序

#include <iostream> #include <vector>using namespace std;void quickSort(vector<int>& a, int low,int high) {if (low < high){int left=low,right=high;int pivot = a[left];while (left < right){while (left < right && a[right] > pivot)right--;a[left] = a[right];while (left < right && a[left] < pivot)left++;a[right] = a[left];}a[left] = pivot;quickSort(a, low, left - 1);quickSort(a, left + 1, high);} }int main(){int num;cin>>num;vector<int> list=vector<int>(num,0);for(int i=0;i<num;i++){cin>>list[i];}int low = 0, high = list.size() - 1;quickSort(list, low, high);for(int i=0;i<num;i++){cout<<list[i]<<" ";}return 0; }

三.冒泡排序

#include <iostream> using namespace std; void bubble_sort(int arr[], int len) {int i, j,temp;for (i = 0; i < len - 1; i++)for (j = 0; j < len - 1 - i; j++)if (arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;} } int main() {int len;cin>>len;int *arr = new int[len];bubble_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;delete []arr;return 0; }

改進(jìn)版：

#include <iostream> using namespace std; void bubble_sort(int arr[], int len) {int i, j,temp,flag;for (i = 0; i < len - 1; i++) {flag = 1;for (j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j + 1]) {flag = 0;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}if (flag)return;} } int main() {int len;cin>>len;int *arr = new int[len];for(int i=0;i<len;i++){cin>>arr[i];}bubble_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;delete []arr;return 0; }

四.選擇排序

#include <iostream> using namespace std; void swap(int arr[],int a,int b){int cen=arr[a];arr[a]=arr[b];arr[b]=cen; } void bubble_sort(int arr[], int len) {for(int i = 0; i < len; i++){int minIndex = i;for(int j = i + 1; j <len; j++){if(arr[j] < arr[minIndex]){minIndex = j;}}swap(arr, i, minIndex);} }int main() {int len;cin >> len;int *arr = new int[len];for (int i = 0; i < len; i++) {cin >> arr[i];}bubble_sort(arr, len);for (int i = 0; i < len; i++)cout << arr[i] << ' ';cout << endl;delete[]arr;return 0; }

五.基數(shù)排序

#include<iostream> using namespace std; int maxbit(int data[], int n) //輔助函數(shù)，求數(shù)據(jù)的最大位數(shù) {int d = 1; //保存最大的位數(shù)int p = 10;for(int i = 0; i < n; ++i){while(data[i] >= p){p *= 10;++d;}}return d; } void radixsort(int data[], int n) //基數(shù)排序 {int d = maxbit(data, n);//最大值的位數(shù)int *tmp = new int[n];int *count = new int[10]; //計(jì)數(shù)器int i, j, k;int radix = 1;for(i = 1; i <= d; i++) //進(jìn)行d次排序{for(j = 0; j < 10; j++)count[j] = 0; //每次分配前清空計(jì)數(shù)器for(j = 0; j < n; j++){k = (data[j] / radix) % 10; //統(tǒng)計(jì)每個(gè)桶中的記錄數(shù)count[k]++;}for(j = 1; j < 10; j++)count[j] = count[j - 1] + count[j]; //將tmp中的位置依次分配給每個(gè)桶for(j = n - 1; j >= 0; j--) //將所有桶中記錄依次收集到tmp中{k = (data[j] / radix) % 10;tmp[count[k] - 1] = data[j];count[k]--;}//等價(jià)于：/* arr=>存放元素的桶（二維數(shù)組）（因?yàn)槊總€(gè)數(shù)字位范圍為0~9，所以取arr[10][待排序數(shù)組元素個(gè)數(shù)]//特殊情況:可能出現(xiàn)所有數(shù)據(jù)在某位是相同值，所有每個(gè)桶需要有待排序數(shù)組元素長度。* int res=0,arr_i_cnt=0;* for(int i=0;i<10;i++){* arr_i_cnt=0;* while(arr_i_cnt<arr_i_len[i]){//arr_i_len用于保存每個(gè)arr[i]實(shí)際的元素個(gè)數(shù)* tmp[res++]=arr[i][arr_i_cnt++];* }* */for(j = 0; j < n; j++) //將臨時(shí)數(shù)組的內(nèi)容復(fù)制到data中data[j] = tmp[j];radix = radix * 10;}delete[]tmp;delete[]count; } int main(){int len;cin>>len;int*a=new int[len];for(int i=0;i<len;i++){cin>>a[i];}radixsort(a,len);for(int i=0;i<len;i++){cout<<a[i]<<" ";}delete []a;return 0; }

六.桶排序

#include<iostream> #include<vector> using namespace std; int len; void bucketSort(int a[],vector<vector<int> > &b);//桶排序函數(shù) void distributeElments(int a[],vector<vector<int> > &b,int digits); void collectElments(int a[],vector<vector<int> > &b); int numOfDigits(int a[]); void zeroBucket(vector<vector<int> > &b);//將b數(shù)組中的全部元素置0 void bucketSort(int a[],vector<vector<int> > &b) {int digits=numOfDigits(a);for(int i=1;i<=digits;i++)//常數(shù)次{distributeElments(a,b,i);collectElments(a,b);if(i!=digits)zeroBucket(b);} } int numOfDigits(int a[])//獲取最大值的位數(shù) {int largest=0;for(int i=0;i<len;i++)//獲取最大值if(a[i]>largest)largest=a[i];int digits=0;while(largest){digits++;largest/=10;}return digits; } void distributeElments(int a[],vector<vector<int> > &b,int digits) {int divisor=10;//除數(shù)for(int i=1;i<digits;i++)divisor*=10;for(int j=0;j<len;j++){int numOfDigist=(a[j]%divisor-a[j]%(divisor/10))/(divisor/10); //numOfDigits為相應(yīng)的(divisor/10)位的值,如當(dāng)divisor=10時(shí),求的是個(gè)位數(shù)int num=++b[numOfDigist][0];//用b中第一列的元素來儲(chǔ)存每行中元素的個(gè)數(shù)b[numOfDigist][num]=a[j];} } void collectElments(int a[],vector<vector<int> > &b) {int k=0;for(int i=0;i<10;i++)for(int j=1;j<=b[i][0];j++)a[k++]=b[i][j]; } void zeroBucket(vector<vector<int> > &b) {for(int i=0;i<10;i++)for(int j=0;j<len+1;j++)b[i][j]=0; } int main() {cin>>len;int *a=new int[len];vector<vector<int> > b=vector<vector<int> >(10,vector<int>(len+1,0));for(int i=0;i<len;i++){cin>>a[i];}bucketSort(a,b);for(int i=0;i<len;i++)cout<<a[i]<<" ";delete []a;return 0; }

七.堆排序

#include <iostream> #include <algorithm> using namespace std; void max_heapify(int arr[], int start, int end) {//建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)int dad = start;int son = dad * 2 + 1;//二叉樹父節(jié)點(diǎn)從0開始的子節(jié)點(diǎn)序列號(hào)while (son <= end){ //若子節(jié)點(diǎn)指標(biāo)在范圍內(nèi)才做比較if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)大小，選擇最大的son++;if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大於子節(jié)點(diǎn)代表調(diào)整完畢，直接跳出函數(shù)return;else //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)和孫節(jié)點(diǎn)比較{swap(arr[dad], arr[son]);dad = son;son = dad * 2 + 1;}} }void heap_sort(int arr[], int len){//初始化，i從最後一個(gè)父節(jié)點(diǎn)開始調(diào)整for (int i = len / 2 - 1; i >= 0; i--)max_heapify(arr, i, len - 1);//先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整(剛調(diào)整的元素之前的元素)，直到排序完畢for (int i = len - 1; i > 0; i--){swap(arr[0], arr[i]);max_heapify(arr, 0, i - 1);} }int main() {int len;cin>>len;int *a = new int[len];heap_sort(a, len);for (int i = 0; i < len; i++)cout << a[i] <<" ";delete []a;return 0; }

總結(jié)

以上是生活随笔為你收集整理的归并排序，快速排序，冒泡排序，选择排序，基数排序，桶排序，堆排序（c++实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。