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

#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 && (size>1); size--) {

int indexOfMax = 0; sorted = true;

for(int i = 1;i

sorted = false;

swap(a[indexOfMax],a[size-1]); for(int i=0;i

//冒泡排序

bool bubble(int a[],int n) {

bool swapped = false; for(int i =0;i

if(a[i]>a[i+1]) {

swap(a[i],a[i+1]); swapped = true; }

for(int x=0;x<6;x++) cout<

cout<<\ }

return swapped; }

void bubbleSort(int a[],int n) {

for (int i =n; i>1 && bubble(a,i);i--); }

//插入排序

void insertionSort(int a[],int n) {

for(int i=1;i

int t=a[i]; int j;

for(j=i-1;j>=0 && t

for(int i=0;i

//基数排序

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) {

int k[MAXK] = {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

b[i] = get_value(array[i],d);

for (i = 0; i < n; i++)

k[b[i]]++;//记录与数组下标相等的数值的个数 for (i=1;i<10;i++)

k[i]+=k[i-1];//储存自己数组下标数值在目标数组对应的位置 for (i=n-1;i>=0;i--)

temp[--k[b[i]]]=array[i]; //将原数组按大小顺序储存到另一个数组

//显示temp数组 for (i=0;i

printf(\ printf(\

for (i = 0; i < n; i++) array[i] = temp[i]; free (temp); free (b); return 1 ; }

int get_value(int a,int d) {

int b=a;

for (;d>0&&a>0;d--) b/=MAXK; return b%MAXK; }

int get_int(void) {

int input; char ch;

while (scanf(\ {

while((ch=getchar())!='\\n') putchar(input);

printf(\as 25,-178,or 3;\\n\ }

return input; }

//快速排序

void quickSort(int s[], int l, int r) {

if (l< r)

{

int i = l, j = r, x = s[l]; while (i < j) {

while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j)

s[i++] = s[j];

while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j)

s[j--] = s[i]; }

s[i] = 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 (a[i] <= a[j])

temp[k++] = a[i++]; else

temp[k++] = a[j++]; }

while (i <= m)

temp[k++] = a[i++];

while (j <= n)

temp[k++] = a[j++];

for (i = 0; i < k; i++)

a[first + i] = temp[i]; }