数据结构之——八大排序算法

排序算法小汇总

  
  

  
  

  
  

交换排序类 冒泡排序（优化）

  冒泡排序一般将前面作为有序区（初始无元素），后面作为无序区（初始元素都在无序区里），在遍历过程中把当前无序区最小的数像泡泡一样，让其往上飘，然后在无序区继续执行此操作，直到无序区不再有元素。
  这块是对老式冒泡排序的一种优化，因为当某次冒泡结束后，可能数组已经变得有序，继续进行冒泡排序会增加很多无用的比较次数，提高时间复杂度。
  所以我们增加了一个标识变量flag，将其初始化为1，外层循环还是和老式的一样从0到末尾，内存循环我们改为从最后面向前面i（外层循环所处的位置）处遍历找最小的，如果在内存没有出现交换，说明无序区的元素已经变得有序，所以不需要交换，即整个数组已经变得有序。

#include<iostream> using namespace std; void sort(int k[] ,int n) { int flag = 1; int temp; for(int i = 0; i < n-1 && flag; i++) { printf("hello\n"); for(int j = n-1; j > i; j--) { flag = 0; /*下面这里和i没关系，注意看这块，从下往上travel，两两比较，如果不合适就调换， 如果上来后一次都没调换，说明下面已经按顺序拍好了，上面也是按顺序排好的，所以完美！ */ if(k[j-1] > k[j]) { temp = k[j-1]; k[j-1] = k[j]; k[j] = temp; flag = 1; } } } } int main() { int k[3] = {0,9,6}; sort(k,3); for(int i =0; i < 3; i++) printf("%d ",k[i]); } 快速排序

快速排序（Quicksort），基于分治算法思想，是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

通俗来说，就是不断的挖坑和填坑

1、其实就是先选择一个基准数,然后这个基准数我们保存为x，那它所在的位置就是一个空出来的坑。

2、我们从右向左迭代，如果遇到比基准数小的数，就将其填到上次挖的坑中，然后它自己在的这个地方就变成了一个新的坑。

3、然后再从左向右迭代，找比基准数大的数，将其填到上次挖的坑中，然后它所在的地方就变成了新的坑。

4、最后要将基准数填入最后的坑中，然后将基准数所在的位置返回，方便下次调用时候使用

//挖坑填数 int adjustArray(int s[],int l, int r) //传入数组和左右的下标 { int i = l,j = r; //分别表示左半边的下标和右半边的下标 int x = s[l]; //默认最左边的数就是挖的第一个坑 while(i < j) //要保证数组中元素最少有两个 { //从右向左迭代，找比基准数小的 while(s[j] >= x && i < j) j--; if(i < j) //找到了比基准数小的 { s[i] = s[j]; //将其填到原来挖的坑的地方上，现在j处又形成了一个新的坑 i++; //i处填入了新的数，所以i++，然后从左往右去找，在左半边比基准数大的数 } //从左向右迭代去找比基准数大的 while(s[i] < x && i < j) i++; if(i < j) { s[j] = s[i]; j--; } } //退出时，要把坑用基准数填回去 s[i] = x; return i; //返回调整后基准数的位置，方便下一次递归调用的时候 }

就这样将原来的数组以返回的基准数所在的位置为中心，分成了两个数组（理论上两个，但在内存中还是在一起挨着的），然后分别对新的两个数组递归进行挖坑和填坑的操作，当先前指示数组左右两边的下标的变量左边的大于或等于（一般都是等于）右边的时候（即数组已经被分的不能被分了），这时候原数组就变成有序的了，因为按照上面的思路，所有左边的都小于右边的，那既然数组都被分的变成一个数一个小数组那就是左边的数比右边的数小，即有序，排序完成！

void quick_sort(int s[], int l, int r) { if(l < r) { int i = adjustArray(s,l,r); //不能将上次的基准数拉入新的两个数组中的任何一个，因为其所在的位置已经是最终对的位置了，它左边的数都比它小，右边的都比它大 quick_sort(s,l,i-1); quick_sort(s,i+1,r); } } 选择排序类 简单选择排序

选择排序就是每次在无序区循环找出一个极值，将其放入指定位置（即进入有序区）来使数组有序，一般来说是让数组的左边作为有序区，右边是无序区。

先从第一个元素到最后一个元素遍历，找出最小的元素，将其和第一个元素互换位置。

再从第二个元素到最后一个元素遍历，找出最小的，和第二个互换位置。