C++实现常见的数据排序算法

C++实现常见的数据排序算法

排序算法原理随便一搜比比皆是，在这里对常见的这些算法用C++实现一下，直接看代码更好理解，上代码。 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.归并排序 6.希尔排序 7.堆排序 8.基数排序 1.冒泡排序

void Buble_sort(int ar[],int n) { for(int i=0;i<n-1;i++) { for(int j=0;j<n-1;j++) if(ar[j]>ar[j+1]) swap(ar[j],ar[j+1]); } printf("Bubble_sort:\n"); print(ar,n); }

2.选择排序

void Select_sort(int ar[],int n) { for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++) { if(ar[i]>ar[j]) swap(ar[i],ar[j]); } } printf("Select_sort:\n"); print(ar,n); }

3.插入排序

void Insert_sort(int ar[],int n) { for(int i=0;i<n-1;i++) { int j; int temp = ar[i+1]; for( j=i+1;j>=0&&ar[j-1]>temp;j--) ar[j] = ar[j-1]; ar[j] = temp; } printf("Insert_sort:\n"); print(ar,n); }

4.快速排序

void Quick_sort(int ar[],int left,int right) { if(left>=right) return; int i=left; int j=right; int temp = ar[left]; while(i!=j) { while(ar[j]>=temp&&i<j) j--; while(ar[i]<=temp&&i<j) i++; if(i<j) swap(ar[i],ar[j]); } ar[left]=ar[i]; ar[i]=temp; Quick_sort(ar,left,i-1); Quick_sort(ar,i+1,right); }

5.归并排序

void merg(int ar[],int left,int right,int mid)//比较并合并 { int temp[20]; int i=left; int p=left; int j=mid; while(i<mid&&j<=right) { if(ar[i]<ar[j]) temp[p++]=ar[i++]; else temp[p++]=ar[j++]; } while(i<mid) temp[p++]=ar[i++]; while(j<=right) temp[p++]=ar[j++]; //将temp中的数付给ar[] p=left; i=left; while(p<=right) ar[i++]=temp[p++]; } void Merge_sort(int ar[],int left,int right)//将数组分开 { if(left<right) { int mid = (right+left)/2; Merge_sort(ar,left,mid); Merge_sort(ar,mid+1,right); merg(ar,left,right,mid+1); } else return; }

6.希尔排序

void Shell_sort(int ar[],int n) { int gap ; for(gap=5;gap>=0;gap--) { for(int i=0;i<gap;i++) { for(int j=i+gap;j<n;j++) { if(ar[j]<ar[j-gap]) { int temp = ar[j]; int k=j-gap; while(k>=0&&ar[k]>temp) { ar[k+gap] = ar[k]; k = k-gap; } ar[k+gap] = temp; } } } } printf("Shell_sort:\n"); print(ar,n); }

7.堆排序

void heapify(int ar[],int n,int i)//堆优化 { int largest=i; int l = 2*i+1; int r = 2*i+2; if(ar[largest]<ar[l]&&l<n) largest = l; if(ar[largest]<ar[r]&&r<n) largest = r; if(largest != i) { swap(ar[largest],ar[i]); heapify(ar,n,largest); } } void Heap_sort(int ar[],int n) { //建堆 int i; for(i=n/2-1;i>=0;i--) heapify(ar,n,i); //排序 for(i=n-1;i>0;i--) { swap(ar[i],ar[0]); heapify(ar,i,0); } printf("Heap_sort:\n"); print(ar,n); }

8.基数排序

void Radix_sort(int ar[],int n) { int d=1,p=10; int i,j; int k,radix=1; int *cont=new int[10]; int *temp=new int[n]; for( i=0;i<n;i++) { while(ar[i]>=p) { p=p*10; d++; } } for( i=1;i<=d;i++) { for( j=0;j<10;j++) cont[j]=0; for( j=0;j<n;j++) { k = (ar[j]/radix)%10; cont[k]++; } for( j=1;j<10;j++) cont[j]=cont[j-1]+cont[j]; for(j = n - 1; j >= 0; j--) { k = (ar[j] / radix) % 10; temp[cont[k] - 1] = ar[j]; cont[k]--; } for(j = 0; j < n; j++) ar[j] = temp[j]; radix = radix * 10; } printf("Radix_sort:\n"); print(ar,n); }

在代码块中print函数代码为

void print(int ar[],int n) { for(int i=0;i<n;i++) cout << ar[i]<< " "; cout<< endl; }

测试代码

int main() { int arr[] = {1,23,16,31,85,20,12,9,95,78,56,68,80,17,26,34,72,99,47,78}; int length = 20; printf("原数组：\n"); print(arr,length); //冒泡排序 Buble_sort(arr,length); //选择排序 Select_sort(arr,length); //插入排序 Insert_sort(arr,length); //快速排序 Quick_sort(arr,0,length-1); printf("Quick_sort:\n"); for(int i=0;i<length;i++) cout<<arr[i]<<" "; cout<<endl; //归并排序 Merge_sort(arr,0,length-1); printf("Merge_sort:\n"); for(int i=0;i<length;i++) cout<<arr[i]<<" "; cout<<endl; //希尔排序 Shell_sort(arr,length); //堆排序 Heap_sort(arr,length); //基数排序 Radix_sort(arr,length); return 0; }

测试结果