1 // 2 // main.cpp 3 // sort 4 // 5 // Created by tsw on 15/8/8. 6 // Copyright (c) 2015年 tsw. All rights reserved. 7 // 8 9 #include <iostream> 10 using namespace std; 11 12 13 14 void print(int arr[],int num){ 15 for (int i=0; i < 9; i++) { 16 cout<<arr[i]<<" "; 17 } 18 cout<<"end"<<endl; 19 } 20 21 //冒泡排序 22 void msort(int arr[],int num){ 23 int i,j,temp; 24 for (i = 0; i< num; i++ ) { 25 for(j = num-1 ; j>= i;j--){ 26 if(arr[j] < arr[j-1]){ 27 temp = arr[j-1]; 28 arr[j-1] = arr[j]; 29 arr[j] = temp; 30 } 31 } 32 } 33 } 34 35 //直接插入排序 36 void insert_sort(int arr[] , int num){ 37 int i,j ,temp; 38 for(i= 1;i < num ;i++){ 39 //cout<<arr[i]<<endl; 40 if(arr[i] < arr[i-1]){ 41 42 temp = arr[i]; 43 for (j=i-1; arr[j] > temp; j--) { 44 arr[j+1] = arr[j]; 45 } 46 arr[j+1] = temp; 47 } 48 } 49 } 50 51 52 // 归并排序 53 void marge(int sr[],int tr1[],int i,int m,int num){ 54 int j,k,l; 55 k = i; 56 j = m+1; 57 for (;i <= m && j<=num; k++) { //左边和右边进行比较 58 if (sr[i]<sr[j]) { 59 tr1[k] = sr[i++]; 60 }else{ 61 tr1[k] = sr[j++]; 62 } 63 } 64 if (i<=m) { //如果左边没有加完则将左边全部加进去 65 for (l = 0; l <= m-i; l++) { 66 tr1[k+l] = sr[i+l]; 67 } 68 } 69 if (j<=num) {//如果右边没有加完则将右边全部加进去 70 for (l=0; l<=num-j ; l++) { 71 tr1[k+l] = sr[j+l]; 72 } 73 } 74 } 75 76 // 归并排序 77 void gb_sort(int sr[],int tr1[],int s,int num){ 78 int m; 79 int tr2[10]; 80 if (s==num) {//递归退出条件 81 tr1[s]=sr[s]; 82 }else { 83 m = (s+num)/2; //找到中间下标 84 gb_sort(sr,tr2,s,m); //将左边添加到数组里边 85 gb_sort(sr,tr2,m+1, num);//将右边添加到数组里边 86 marge(tr2,tr1,s,m,num); //将左边和右边进行排序 87 } 88 } 89 90 void swap(int arr[],int a,int b){ 91 int temp; 92 temp = arr[a]; 93 arr[a] = arr[b]; 94 arr[b] = temp; 95 } 96 97 int part(int arr[],int low,int high){ 98 99 int m,temp; 100 m = low+(high-low)/2; // 以下为三次取中 101 if (arr[low]>arr[high]) { 102 swap(arr,low,high); 103 } 104 if (arr[m]>arr[high]) { 105 swap(arr,m,high); 106 } 107 if (arr[m]>arr[low]) { 108 swap(arr,low,m); 109 }// 以下为三次取中 110 temp = arr[low]; 111 112 while (low<high) { 113 while (arr[high]>=temp && low < high) { 114 high--; //如果arr[high]大于中间值的话 high向后移动一位 115 } 116 arr[low] = arr[high]; //用后边的值去覆盖前边的值 117 118 while (arr[low] <= temp && low < high) { 119 low++; 120 } 121 arr[high] = arr[low]; 122 123 } 124 arr[low] = temp; 125 126 127 return low; 128 } 129 130 131 132 void fast_sort(int arr[],int low ,int high){ 133 134 int p; 135 while(low<high) { //或者用if 136 p = part(arr,low,high); 137 fast_sort(arr, low , p - 1); 138 low = p + 1; 139 //fast_sort(arr, p + 1 , high); 140 } 141 } 142 143 144 145 146 //堆排序 147 148 void adjust(int arr[],int s,int m){ 149 int temp,i; 150 temp = arr[s]; 151 152 for ( i = 2 * s +1 ; i <= m; i =i * 2+1) { //当数组是从0开始的二叉树的结构将是 0 1 2 3 4 5 6 7 8 0对应的两个子树为 1和 2; 1对应的两个子树为3和4 一次类推 153 if (i < m && arr[i] < arr[i+1]) { //判断左孩子节点是否小于右孩子节点,小于的话将i志向右孩子节点 154 i++; 155 } 156 if (temp >= arr[i]) { //如果根节点大于或等于两个子节点则不用改变 157 break; 158 } 159 arr[s] = arr[i]; 160 s = i; 161 } 162 arr[s] = temp; 163 } 164 165 166 void d_sort(int arr[],int num){ 167 int i , temp; 168 for (i = num/2-1; i >= 0 ; i--) { 169 adjust(arr,i,num-1); 170 print(arr, 9); 171 172 } 173 cout<<"buile end"<<endl; 174 for (i = num-1; i >= 0; i--) { 175 temp = arr[i]; 176 arr[i] = arr[0]; 177 arr[0] = temp; 178 adjust(arr,0,i-1); // 必须是i-1 ,因为当上一次交换过之后最大的值已经放到最后了,所以不用再进行交换了 179 print(arr, 9); 180 } 181 } 182 183 184 void shell_sort(int arr[],int num){ 185 int incriment = num-1; 186 int i , temp , j; 187 do{ 188 incriment = incriment/3; //跳跃值的不同,排序的次数也不同 189 for (i = incriment; i < num; i++) { 190 if (arr[i] < arr[i-incriment]) { 191 temp = arr[i]; 192 for (j = i - incriment; j >= 0 && arr[j] > temp ; j-=incriment) { //循环判断当前值是否小与前一个位置的值,如果小与则替换 193 arr[j+incriment] = arr[j]; 194 } 195 arr[j+incriment] = temp; 196 } 197 } 198 print(arr, 9); 199 200 }while (incriment>1); //跳跃值不能为1否则将会进入死循环 201 } 202 203 204 205 206 int main(int argc, const char * argv[]) { 207 // insert code here... 208 int arr[] = {3,4,12,8,6,2,9,7,1};//{50,10,90,30,70,40,80,60,20};// 209 //msort(arr, 9); 210 //insert_sort(arr, 9); 211 //gb_sort(arr, arr, 0, 9-1); 212 //fast_sort(arr, 0, 8); 213 //d_sort(arr,9); 214 shell_sort(arr, 9); 215 print(arr, 9); 216 std::cout << "Success "; 217 return 0; 218 }