《数据结构实验二排序算法代码实现》由会员分享,可在线阅读,更多相关《数据结构实验二排序算法代码实现(6页珍藏版)》请在金锄头文库上搜索。
1、#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 = false;for(int size = n;!sorted siz
2、e-)int indexOfMax = 0;sorted = true;for(int i = 1;iai+1)swap(ai,ai+1);swapped = true;for(int x=0;x1 /插入排序void insertionSort(int a,int n)for(int i=1;i=0 j-)aj+1=aj;aj+1=t;for(int i=0;i=0;i-) temp-kbi=arrayi; /将原数组按大小顺序储存到另一个数组 /显示 temp数组 for (i=0;i0d-) b/=MAXK; return b%MAXK; int get_int(void) int in
3、put; 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 s, int l, int r) if (l= x) / 从右向左找第一个小于 x的数 j-; if(i j) si+ = sj; while(i j & si x) / 从左向右找第一个大于等于
4、 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 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+;elsetempk+ = aj+;while (i = m)tempk+
5、= 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 (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)coutai ;coutn;mergearray(a,
6、 first, mid, last, temp); /再将二个有序数列合并for (int i = 0; i last+1; +i)coutai ;coutn; 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,1,3,4;for(int i=0;i6;i+)coutdi ;coutn;selectionSort(d,6);coutn;bubbleSort(d,6
7、);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:; for(k=0;klen;k+) coutarrayk,; coutn;coutn;int arr = 34,65,12,43,67,5,78,10,3,70;MergeSort(arr, 10);for (int i = 0; i 10; +i)coutarri ;return 0;