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

1、-作者xxxx-日期xxxx数据结构实验二排序算法代码实现【精品文档】#include#include #include #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)bool sorted =

2、 false;for(int size = n;!sorted & (size1); size-)int indexOfMax = 0;sorted = true;for(int i = 1;isize; i+)if (aindexOfMax= ai)indexOfMax = i;elsesorted = false;swap(aindexOfMax,asize-1);for(int i=0;in;i+) coutai ; coutn;/冒泡排序bool bubble(int a,int n)bool swapped = false;for(int i =0;iai+1)swap(ai,ai+

3、1); swapped = true;for(int x=0;x6;x+) coutax ; cout1 & bubble(a,i);i-);/插入排序void insertionSort(int a,int n)for(int i=1;i=0 & taj;j-)aj+1=aj;aj+1=t;for(int i=0;in;i+) coutai ; coutn;/基数排序void radixSort(int* a,int n,int d) for (int i=0;i=d;i+) countSort(a,n,i); int countSort (int *array, int n,int d)

4、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;in;i+) bi = get_value(arrayi,d); for (i = 0; i n; i+) kbi+;/记录与数组下标相等的数值的个数 for (i=1;i=0;i-) temp-kbi=arrayi; /将原数组按大小顺序储存到另一个数组 /显示temp数组 for (i=0;i

5、n;i+) printf(%d ,tempi); printf(n); for (i = 0; i 0&a0;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 quick

6、Sort(int s, int l, int r) if (l r) int i = l, j = r, x = sl; while (i j) while(i = 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); /归并排序 void mergearray(int a, int first, int mid, int la

7、st, 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 k; i+) afirst + i = tempi;void mergesort(int a, int first, int last, int temp) if (fir

8、st 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) coutai ; coutn; mergearray(a, first, mid, last, temp); /再将二个有序数列合并for (int i = 0; i last+1; +i) coutai ; coutn; bool MergeSort(int a, int n) int *p = ne

9、w intn; if (p = NULL) return false; mergesort(a, 0, n - 1, p); delete p; return true;int main()int d6=3,2,5,1,3,4;for(int i=0;i6;i+) coutdi ; coutn;selectionSort(d,6);coutn;bubbleSort(d,6);coutn;insertionSort(d,6);coutn;int n = 12; int p12 = 323,31,13,25,2,111,332,54,253,14,544,435; for (int i=0;in;i+) printf(%d ,pi);coutn; radixSort(p,n,3); for (int i=0;in;i+) printf(%d ,pi); coutn; coutn; int array=34,65,12,43,67,5,78,10,3,70,k; int len=sizeof(array)/sizeof(int); coutThe orginal arrayare:; for(k=0;klen;k+) coutarrayk,; coutn; quickSort(array,0,len-1); coutThe sorted arrayare