冒泡、选择、插入排序
1 #include2 #include 3 #include 4 5 //数组元素的个数 6 #define SIZE 15 7 8 //初始化数组 9 void initArray(int *arr, int len); 10 11 //打印数组元素 12 void printArray(int *arr, int len); 13 14 //交换两个数 15 void swap(int *a, int *b); 16 17 //冒泡排序 18 void bubbleSort(int *arr, int len); 19 20 //选择排序 21 void selectSort(int *arr, int len); 22 //返回最大值元素的下标 23 int max_key(int *arr, int beg, int end); 24 25 //插入排序 26 void insertSort(int *arr, int len); 27 28 int main() 29 { 30 int arr[SIZE]; 31 initArray(arr,SIZE); 32 printArray(arr,SIZE); 33 // bubbleSort(arr,SIZE); 34 // selectSort(arr,SIZE); 35 insertSort(arr,SIZE); 36 printArray(arr,SIZE); 37 return 0; 38 } 39 40 void initArray(int *arr, int len) 41 { 42 int i; 43 //随机生成数组元素 44 for(i = 0; i < len; i++) 45 arr[i] = rand() % 1000; 46 } 47 48 void printArray(int *arr, int len) 49 { 50 int i; 51 for(i = 0; i < len; i++) 52 printf("%4d",*(arr+i)); 53 printf("\n"); 54 } 55 56 //通过位操作交换两个数 57 void swap(int *a, int *b) 58 { 59 *a ^= *b;//记录差异 60 *b ^= *a;//翻转 61 *a ^= *b;//翻转 62 } 63 64 //来回冒泡排序 65 void bubbleSort(int *arr, int len) 66 { 67 int index;//工作指针 68 int top;//记录右边排好序的第一个元素的下标 69 int bottom;//记录左边排好序的最后一个元素的下标 70 71 top = len; 72 bottom = -1; 73 74 while(bottom <= top) 75 { 76 //从左往右 77 for(index = bottom+1; index < top-1; index++) 78 if(arr[index] > arr[index+1]) 79 swap(&arr[index],&arr[index+1]); 80 top--; 81 //从右往左 82 for(index = top-1; index > bottom+1; index--) 83 if(arr[index] < arr[index-1]) 84 swap(&arr[index],&arr[index-1]); 85 bottom++; 86 } 87 } 88 //返回最大元素的下标 89 int max_key(int *arr, int beg, int end) 90 { 91 int i; 92 int largest = beg; 93 for(i = beg+1; i <= end; i++) 94 if(arr[i] > arr[largest]) 95 largest = i; 96 return largest; 97 } 98 //选择排序 99 void selectSort(int *arr, int len)100 {101 int i, max;102 for(i = len-1; i > 0; i--)103 {104 max = max_key(arr,0,i);105 swap(&arr[max],&arr[i]);106 }107 }108 109 //插入排序110 void insertSort(int *arr, int len)111 {112 int i;//工作指针113 int first_unsorted;//第一个未排序元素下标114 int current;//暂存待插入的元素115 116 for(first_unsorted = 1; first_unsorted < len; first_unsorted++)117 if(arr[first_unsorted] < arr[first_unsorted-1])118 {119 //暂存元素120 current = arr[first_unsorted];121 i = first_unsorted;122 do{123 arr[i] = arr[i-1];124 i--;125 }while(i > 0 && arr[i-1] > current);126 //插入元素127 arr[i] = current;128 }129 }