首页 > 代码库 > 冒泡排序,插入排序,归并排序,快速排序的学习笔记
冒泡排序,插入排序,归并排序,快速排序的学习笔记
这几个很基础的排序非常有用,我重新整理了下代码
1 #include<iostream> 2 #include<algorithm> 3 4 using namespace std; 5 6 void Bouble_Sort(int * Arry,int Lenth) //冒泡排序 7 { 8 int i,k; 9 10 int flag = 0; 11 12 for(i = Lenth - 1;i >= 0; i--) 13 { 14 for(k=0;k<i;k++) 15 { 16 if(Arry[k] > Arry[k+1]) 17 { 18 swap(Arry[k],Arry[k+1]); //如果存在前一个比后一个大的情况,则交换两个数字 19 20 flag = 1; //Flag的作用是判断 这个数组是否已经排完序了,如果已经是顺序了,就不再进行排序了 21 } 22 } 23 24 if(flag == 0) 25 break; 26 } 27 } 28 29 //插入排序 30 31 void Insert_Sort(int * Arry,int Lenth) 32 { 33 int i,k; 34 35 int TempNumb = 0 ; 36 37 for(i = 0; i < Lenth; i++) 38 { 39 TempNumb = Arry[i]; //从0到i的所有数 40 41 for(k = i;k>0 && Arry[k] > TempNumb;k++) //如果有这个数的前面几位,大于了他,那么这个数的后面几位全部向后移动一位 42 { 43 Arry[k+1] = Arry[k]; //整体向后移动 44 } 45 46 Arry[k] = TempNumb; 47 } 48 } 49 /* 50 说下插入排序的思路: 一开始选择的数字在最左边,所以没的比较,保持在最左端,然后第二个数会和第一个数比较,如果较大 51 则第一个数会向后移动一位,注意这里移动的范围始终在最外面这层循环,即i的大小。 52 */ 53 54 55 //归并排序 56 void Merge(int * Arry,int * TempArry,int Left,int Right,int Rightend) 57 { 58 int LeftEnd = Right - 1; 59 60 int totalNumb = Rightend - Left + 1; 61 62 int Pointer = Left; 63 64 int i; 65 66 while(Left <= LeftEnd && Right <= Rightend) 67 { 68 if(Arry[Left] < Arry[Right]) 69 TempArry[Pointer++] = Arry[Left++]; 70 else 71 TempArry[Pointer++] = Arry[Right++]; 72 } 73 74 while(Left <= LeftEnd) 75 TempArry[Pointer++] = Arry[Left++]; 76 77 while(Right <= Rightend) 78 TempArry[Pointer++] = Arry[Right++]; 79 80 for(i=0;i<totalNumb;i++,Rightend--) 81 { 82 Arry[Rightend] = TempArry[Rightend]; 83 } 84 85 } 86 87 void Merge_Sort(int * Arry,int * TempArry,int Left,int Rightend) //插入排序使用了分治的思路 88 { 89 int Mid; 90 91 if(Rightend > Left) 92 { 93 Mid = (Left + Rightend) / 2; 94 95 Merge_Sort(Arry,TempArry,Left,Mid); 96 97 Merge_Sort(Arry,TempArry,Mid+1,Rightend); 98 99 Merge(Arry,TempArry,Left,Mid+1,Rightend); 100 } 101 } 102 103 int Partation(int * Arry,int Low,int High) //寻找中间值 104 { 105 int KeyNumb; 106 107 KeyNumb = Arry[Low]; // 首先默认最左端的值为KeyNumb 108 109 while(Low < High) 110 { 111 while(Low < High && Arry[Low] < Arry[High]) //当 High > Low的时候, Low指针向前移动,一直到 arry.high < arry.Low, 112 Low++; 113 114 swap(Arry[Low],Arry[High]); //交换两个值 115 116 while(Low < High && Arry[High] > Arry[Low]) 117 High--; 118 119 swap(Arry[Low],Arry[High]); 120 } 121 122 return Low; //此时Low所处的位置,arry[Low] 已经排好序了,也就是该位置是最终位置 123 } 124 125 126 127 void Quick_Sort(int * Arry,int Low,int High) //快速排序 128 { 129 int KeyNumb; 130 131 if(High > Low) 132 { 133 KeyNumb = Partation(Arry,Low,High); //分治算法 134 135 Quick_Sort(Arry,Low,KeyNumb - 1); //对左边进行递归 136 137 Quick_Sort(Arry,KeyNumb+1,High); //对右边进行递归 138 139 } 140 } 141 142 int main() 143 { 144 int i; 145 146 int Arry[10] = {10,9,8,7,6,5,4,3,2,1}; 147 148 int TempArry[10] = {0}; 149 150 //Bouble_Sort(Arry,10); 151 152 //Insert_Sort(Arry,10); 153 154 //Merge_Sort(Arry,TempArry,0,10); 155 156 //Quick_Sort(Arry,0,9); 157 158 for(i=0;i<10;i++) 159 { 160 cout << Arry[i] <<‘ ‘; 161 } 162 }
冒泡排序,插入排序,归并排序,快速排序的学习笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。