冒泡排序 基本思想：给定一组数，将相邻的两个数进行比较，如果后面的数大于前面的数，则进行交换。 给定一组数20，65，13，46，68，23，9，34，89，10 这是一趟冒泡排序，用红色标记的数都是在这趟排序中位置有过移动的数，第一趟排序的结果是：20，13，46，65，23，9，34，68，10，89。可以看出，89是这组数中最大的数，所以一趟排序可以将最后一个数的位置找对，第二趟排序就是倒数第二个数，以此类推。。。所以，按照这种方法，有n个数的排序，至少要进行n-1次排序。 下面是基本冒泡排序的代码：
for(int i = 0; i < n; ++i) { for(int j = 0; j < n-i-1; ++j) { if(arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }但是这样效率并不是很高，因为如果在某趟排序中没有发生数据交换，则就不用继续往下进行了，可我们刚才写的程序还会继续再排，直到程序终止。要进行改进，我们应该在程序中添加一个标志位，初始值为假，如果排序中有数据交换，则将其置为真，如果为假，则不进行下一次排序。具体代码如下：
bool flag = false; for(int i = 0; i < n; ++i) { for(int j = 0; j < n-i-1; ++j) { if(arr[j] > arr[j+1]) { int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; flag = true; } if(!flag) { break; } flag = false;```` } }可以看出，冒泡排序的时间复杂度接近于O(n^2),而空间复杂度是O(1),因为不需要额外开辟空间。
选择排序 还是拿20，65，13，46，68，23，9，34，89，10这组数来说。 基本思想：先选定一个基数20当作最小值Min，并记下它的下标index，然后从65开始和最小值20进行比较，如果小于最小值20，就将最小值Min重新赋值为当前的值，并将下标改为当前值对应的下标。一轮数组遍历完后，Min中保存的将是该数组中最小的数，index则保存的是他的下标。将当前下标和最初的index进行比较，如果不相等，则进行交换，将最小的数交换到第一个位置。下一次，再选第二个数作为最小值，从第三个数开始比较，以此类推。。。 看看代码就一目了然了：
for(int i = 0; i < n; ++i) { int min = arr[i]; int min_index = i; for(int j = i+1; j < n; ++j) { if(arr[j] < min)//如果当前值小于民Min,则给Min重新赋值 { min = arr[j]; min_index = j; } } if(min_index != i) { int temp = arr[i]; arr[i] = arr[min_index]; arr[min_index] = temp; } }可以看出，选择排序和冒泡排序的平均时间复杂度和空间复杂度是一样的，分别为O(n^2) 和O(1)。
交换排序 基本思想：和选择排序比较像，不同之处在于选择排序是在一趟比较完成之后才进行交换，而交换排序是每比较一次交换一次，相对于来说效率就有点低了。 看代码：
for(int i = 0; i < n ;++ n) { for(int j = i+1;j < n; ++j) { if(arr[i] > arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } }平均时间复杂度同样为O(n^2),空间复杂度为O(1)。
插入排序 基本思想：不同于其他的排序，插入排序的外层循环是从下标1开始递增的，内部的循环是从i-1开始递减的。每次进行第二层循环之前，先用一个临时变量记下当前arr[i]的值，然后执行第二层循环，用arr[j]和临时变量中存的值进行比较，如果满足条件则进行交换,最后将临时变量插入到合适的位置。
for(int i = 1;i < n; ++i) { int tmp = arr[i]; for(int j = i-1; j >= 0; --j) { if(arr[j] < tmp) { break; } arr[j+1] = arr[j]; } arr[j+1] = tmp; }平均时间复杂度O(n^2),空间复杂度O(1)。
快速排序 基本思想：快速排序是对冒泡排序的一种改进，首先选择一个基数，然后将该数作为节点，将待排序数组分为基本有序的两组，其中节点左边的数均比它小，右边的均比它大，然后按照同样的方法分别对两部分继续进行排序，从而达到整体有序。 还是拿20，65，13，46，68，23，9，34，89，10这组数来说。 其中有两个索引low和high，一个代表数组的开始，一个代表数组的结束，arr[low]即20作为基数，用临时变量存起来。首先从high开始，遇到一个比20小的数，就将其赋值给arr[low]，然后又从low开始，遇到比20大的数就将其赋值给arr[high]，，一直重复，知道low=high,此时，将tmp复制给arr[low]。一趟下来可以发现，20左边的数均小于塔，右边的数均大于它。
椭圆形表示的是本次位置进行变动的数。再看看代码或许更加容易理解。
int partation(int arr[],int left,int right) { int key = arr[left]; for(;left<right;) { while(right > left && right >0) { if(arr[right] < key) { arr[left] = arr[right]; left++; break; } right--; } while(left < right && left < 10) { if(arr[left] > key) { arr[right] = arr[left]; right--; break; } left++; } } arr[left] = key; return left; } void quick(int arr[],int left,int right) { if(left < right) { int base = partation(arr,left,right); quick(arr,left,base-1); quick(arr,base+1,right); } }这里对快速排序的分割部分进行了封装，用的时候只需在主函数中调用quick函数就可以了。quick部分采用的是递归的写法。当然不止这一种写法，其他的我就不列举了，自己研究研究吧。 平均时间复杂度：O(n*log(n)),空间复杂度：O(log(n))。
shell排序 基本思想：希尔排序是插入排序的一种，不同的是插入排序的增量是1，而希尔排序的增量是可以自己定义的。 还是拿20，65，13，46，68，23，9，34，89，10这组数来说。规定增量为3的情况下，上面的数就会被分成3组（相同颜色为一组）。 比较的时候，就是相同颜色的数字进行比较或者交换。当然，如果增量为1的话，那就是插入排序了。因此我们可以在理解插入排序的基础上写shell排序的代码。
for(int i = gap;i < len; i = i+gap) { int temp = arr[i]; for(int j = i-gap; j >= 0; j = j-gap) { if(arr[j] < temp) { break; } arr[j+gap] = arr[j]; } arr[j+gap] = temp; }对比插入排序的代码可以发现，这里用gap，也就是所谓的增量替换了插入排序中的1。虽然思想是相同的，但是经过改进之后，效率提高了很多，而且增量的值不同，效率业有可能不同。感兴趣的同学可以测试一下。它的时间复杂度和空间复杂度分别为O((nlog(n))^2)和O(1)。
堆排序 基本思想:我觉得堆排序是一个比较麻烦，想起来比较困难的一个排序，但是它的效率相比前面的排序都比较高。首先，需要建立一个大根堆，即从堆顶到堆底，数字越来越小。其实最麻烦的也就在这块。建好大根堆之后，堆顶的元素应当是数组中最大的数，而堆中的最后一个元素必然是最小的数，因此只要将两个数交换就可以了，这样最大的那个数的位置就确定了，接下来继续将剩余的数调成大根堆，然后再进行交换，就以这样的方式一直重复数组的长度次就可以排好序了。 还是拿上面那组数来说，刚开始建立的堆是这样子的： 整理成大根堆是这样子的： 第一次交换后是这样子的： 接下来就继续调整成大根堆，继续交换。。。。。。下面是代码，首先是调整成大根堆的代码：
void adjust(int *arr,int start,int len) { int temp = arr[start]; for(int i=2*start+1;i<len;i=2*i+1) { if(i+1<len && arr[i+1] > arr[i]) { i = i + 1; } if(arr[i] > tmp) { arr[start] = arr[i]; } else if(arr[i] < tmp) { break; } start = i; } arr[start] = tmp; }接下来是进行交换，并在每次交换之后重新调整成大根堆：
int swap(int *arr,int len) { for(int i = len-1;i > 0;--i) { int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; adjust(arr,0,i) } } 在主函数中，我们首先调用adjust函数将待排序数组调整成大根堆，然后再调用swap函数进行排序。 时间复杂度：O(n*log(n)),空间复杂度：O(1)。归并排序 基本思想：我觉得归并排序和shell排序有点像，都需要一个增量，不同的是归并排序的增量每次都会发生变化，而shell排序的增量在整个排序中可以是固定的。我觉得还是画图说更清楚一点。 图片上给出的只是gap=0时的情况，当然，在循环的过程中，gap是每次都会改变的，但是原理都是相同的。再结合代码看看。
void meger(int *arr,int len,int gap) { int *buff = (int *)malloc(sizeof(int) * len); assert(buff != NULL); int tmp; int k = 0; int L1 = 0; int H1 = L1 + gap; int L2 = H1 + 1; int H2 = L2 + gap > (len-1) ? (len-1) : L2+gap; while (L2 < len) { while(L1 <= H1 && L2 <= H2) { if (arr[L1] <= arr[L2]) { buff[k++] = arr[L1++]; } else { buff[k++] = arr[L2++]; } } while (L1 <= H1) { buff[k++] = arr[L1++]; } while (L2 <= H2) { buff[k++] = arr[L2++]; } L1 = H2 + 1; H1 = L1 + gap; L2 = H1 + 1 ; H2 = L2 + gap > (len-1) ? (len-1) : L2+gap; } while (L1 < len) { buff[k++] = arr[L1++]; } for (int i=0;i<len;i++) { arr[i] = buff[i]; } free(buff); } void meger_sort(int *arr,int len) { for (int gap=1;gap<len;gap=gap*2) { meger(arr,len,gap-1); } }结合代码和图片应该更容易理解。 时间复杂度：O(n*log(n)),空间复杂度：O(n)。
暂时就总结这么多吧。其实每个排序都挺相似的，还是要认真研究才行。
