数据结构实验二排序算法代码实现

1、#include<iostream>#include <stdio.h> #include <stdlib.h> #define MAXK 10 using namespace std;int get_int(void); int countSort (int*array,int n,int d); int get_value(int a,int d); void radixSort(int* a,int n,int d); void quickSort(int a,int,int); /选择排序 void selectionSort(int a,int n

2、)bool sorted = false;for(int size = n;!sorted && (size>1); size-)int indexOfMax = 0;sorted = true;for(int i = 1;i<size; i+)if (aindexOfMax<= ai)indexOfMax = i;elsesorted = false;swap(aindexOfMax,asize-1);for(int i=0;i<n;i+) cout<<ai<<" " cout<<"n&

3、quot;/冒泡排序bool bubble(int a,int n)bool swapped = false;for(int i =0;i<n-1;i+)if(ai>ai+1)swap(ai,ai+1); swapped = true;for(int x=0;x<6;x+) cout<<ax<<" " cout<<"n"return swapped; void bubbleSort(int a,int n)for (int i =n; i>1 && bubble(a,i);i-)

4、;/插入排序void insertionSort(int a,int n)for(int i=1;i<n;i+)int t=ai;int j;for(j=i-1;j>=0 && t<aj;j-)aj+1=aj;aj+1=t;for(int i=0;i<n;i+) cout<<ai<<" " cout<<"n"/基数排序void radixSort(int* a,int n,int d) for (int i=0;i<=d;i+) countSort(a,n,i); int

5、countSort (int *array, int n,int d) int kMAXK = 0; int * temp,*b; int i; temp = (int *) malloc (sizeof (int)*n); b = (int *) malloc (sizeof (int)*n); if (NULL = temp) return 0 ; for (i=0;i<n;i+) bi = get_value(arrayi,d); for (i = 0; i < n; i+) kbi+;/记录与数组下标相等的数值的个数 for (i=1;i<10;i+) ki+=ki-

6、1;/储存自己数组下标数值在目标数组对应的位置 for (i=n-1;i>=0;i-) temp-kbi=arrayi; /将原数组按大小顺序储存到另一个数组 /显示temp数组 for (i=0;i<n;i+) printf("%d ",tempi); printf("n"); for (i = 0; i < n; i+) arrayi = tempi; free (temp); free (b); return 1 ; int get_value(int a,int d) int b=a; for (;d>0&&

7、;a>0;d-) b/=MAXK; return b%MAXK; int get_int(void) int input; char ch; while (scanf("%d",&input)!=1) while(ch=getchar()!='n') putchar(input); printf(" is not an integer.nPlease enter an integer value,such as 25,-178,or 3;n"); return input; /快速排序 void quickSort(int

8、s, int l, int r) if (l< r) int i = l, j = r, x = sl; while (i < j) while(i < j && sj>= x) / 从右向左找第一个小于x的数 j-; if(i < j) si+ = sj; while(i < j && si< x) / 从左向右找第一个大于等于x的数 i+; if(i < j) sj- = si; si = x; quickSort(s, l, i - 1); / 递归调用 quickSort(s, i + 1, r); /归并

9、排序 void mergearray(int a, int first, int mid, int last, int temp) int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) if (ai <= aj) tempk+ = ai+; else tempk+ = aj+; while (i <= m) tempk+ = ai+; while (j <= n) tempk+ = aj+; for (i = 0; i <

10、k; i+) afirst + i = tempi;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); /右边有序 for (int i = 0; i < last+1; +i) cout<<ai<<" " cout<<"n&

11、quot; mergearray(a, first, mid, last, temp); /再将二个有序数列合并for (int i = 0; i < last+1; +i) cout<<ai<<" " cout<<"n" bool MergeSort(int a, int n) int *p = new intn; if (p = NULL) return false; mergesort(a, 0, n - 1, p); delete p; return true;int main()int d6=3,2,5

12、,1,3,4;for(int i=0;i<6;i+) cout<<di<<" " cout<<"n"selectionSort(d,6);cout<<"n"bubbleSort(d,6);cout<<"n"insertionSort(d,6);cout<<"n"int n = 12; int p12 = 323,31,13,25,2,111,332,54,253,14,544,435; for (int i=0;i&l

13、t;n;i+) printf("%d ",pi);cout<<"n" radixSort(p,n,3); for (int i=0;i<n;i+) printf("%d ",pi); cout<<"n" cout<<"n" int array=34,65,12,43,67,5,78,10,3,70,k; int len=sizeof(array)/sizeof(int); cout<<"The orginal arrayare:" for(k=0;k<len;k+) cout<<arrayk<<"," cout<<"n" quickSort(array,0,len-1); cout<<"The sorted arrayare:" for(k=0;k<len;k+) cout<<a