1.冒泡排序1.1冒泡排序概念与总思路通过重复遍历待排序数组每次都将相邻两个元素进行比较每轮都会把一个最大的元素放到末尾就像气泡缓缓上浮一样因此得名冒泡排序1.2 代码思路通过两层for循环的嵌套加上参数设计以及判断是否发生交换的标记变量组合而成参数为数组名以及数组长度一第一层for循环标记变量第一层for循环用于遍历整个数组并定义标记变量falgfor (i 0; i n; i) { int flag 0 }二二层for循环比较相邻变量本轮是否发生交换判断第二层for循环用于相邻变量的比较如果需要发生交换就将标记变量置为 1并在第二层for循环外设置一个判断条件如果一轮下来flag仍为0证明没有发生交换for (int i 0; i n; i) { int falg 0 for (int j 0; j n-i-1 ; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); falg 1 } } if (flag 0) { break; } }完整代码如下void Bubble(int* a, int n) { for (int i 0; i n; i) { int falg 0 for (int j 0; j n-i-1 ; j) { if (a[j] a[j 1]) { swap(a[j], a[j 1]); falg 1 } } if (flag 0) { break; } } }2.快速排序2.1 快速排序概念与总思路快速排序是Hoare在1962年提出的一种二叉树结构的交换排序方法将一个数组看成是树状结构不停的划分左右两个部分具体思路就是通过划定一个范围在此范围中找出一个关键值keyi将关键值放到数组的中间使数组左边的数据都比关键值要小数组右边的数据都比关键值要大然后将范围缩小进行同样的操作原本的范围是整个数组通过递归操作将keyi值往左与往右的数组设定为新的范围在新的范围内找出自己范围内的关键值通过不断的将范围缩小并在新范围内进行调整缩小到范围只剩两个数据的时候进行最后一次调整然后结束。2.2 代码思路以及两种找关键值(keyi)的方法思路是利用递归方法以及查找关键值此两种找keyi的方法都用到了一个共同的递归函数我们将其命名为QuickSort需要传递的参数有数组名int* a数组的头尾int left int right思路分为3步一设置递归终止条件我们不妨将left 与 right 看作指向数组某个位置的箭头当左箭头与右箭头相遇时递归就应该终止所以当left right 时递归一定结束为了让限制的范围更大我们加上左箭头超过右箭头的限制if(left right) { retutn; }二定义keyi并调用查找函数定义keyi 来接收返回值int keyi _QuickSort_Hoare(a, left, right);//Hoare //int keyi _QuickSort_Lomuto(A, Left, right);//Lomuto //二者只有命名区别三递归左右序列通过对原函数的两次调用完成该任务QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right);完整的主函数代码就是//1 if(left right) { retutn; } //2 int keyi _QucikSort(a, left, right);//调用对应查找函数 //3 QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right);2.2.1 hoare 法找keyihoare法找keyi方法分为6步总体思路为定义keyi通过left找大于keyi的数right找小于keyi的数再将left处的数与right的数进行交换循环往复以达到左边小右边大的目的一定义与标记keyi在最左侧初始将keyi放道left的位置int kyei left;二隔壁开找因为初始了keyi在最左侧找的时候不用与自己比较节省一次循环次数left;三3while循环查找第一个循环用于限定范围left right防止越界第二和第三个循环用于查找找最大与最小其中在第二和第三个while循环中也要加入第一个while循环的限制条件以免循环内的调整导致了越界访问while (left right) { while(left right a[left] a[keyi]) { left; } while (left right a[right] a[keyi]) { right--; } }四条件l r 交换此次交换也在第一个while 循环的范围内因此也需要加上第一个while循环的限制条件防止数组越界访问while (left right) { while(left right a[left] a[keyi]) { left; } while (left right a[right] a[keyi]) { right--; } if (left right) { Swap(a[left], a[right--]); } }五keyi r 交换keyi值移中因为right 找的是最小值所以最后将keyi 处的值与right处进行交换就可以保证右侧都是大于keyi处的值左侧都是小于keyi处的值Swap(a[keyi], a[right]);六返回right返回中间值return right;完整的Hoare方法找keyi 的代码为int Q1(int* a, int left, int right) { int keyi left; left; while (left right) { while(left right a[left] a[keyi]) { left; } while (left right a[right] a[keyi]) { right--; } if (left right) { Swap(a[left], a[right--]); } } Swap(a[keyi], a[right]); return right; }2.2.2 lomuto 前后指针法找keyilomuto法的思路是通过设置一个前后指针前者负责探路从左往右查找比基准值要小的进行交换就使得小的数都排在了基准值的左边一定义keyi 以及前后指针prev 与 cur将keyi 与 prev 初始定义在最左侧cur定义为prev 后面一个位置int keyi left; int prev left, cur prev 1;二while循环条件cur不越界保证探路指针cur 不越界while (cur right) { }三cur prev 条件交换先来看代码while (cur right) { if (a[cur] a[keyi] prev ! cur) { Swap(a[cur], a[prev]); } cur; }先进行cur处值与基准值的比较如果找到比基准值小的就进行逻辑和后面的处理保证prev处的值不与cur处的值相等且进行一个前置加加与不等于cur处值得判断保证prev与cur的指向不会重合。cur保证一直向后探路四keyi prev 交换 keyi 移中将基准值放在中间Swap(a[keyi], a[prev]);五返回prevreturn prev;完整代码void Q2(int* a, int left, int right) { int keyi left; int prev left, cur prev 1; while (cur right) { if (a[cur] a[keyi] prev ! cur) { Swap(a[cur], a[prev]); } cur; } Swap(a[keyi], a[prev]); return prev; }