插入排序：
插入排序过程
基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想。
直接插入排序：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
插入排序
代码实现：
1. //插入排序： 2. public void insertSort(int[]arr){ 3. 4. for (int i = 1; i < arr.length ; i++) { 5. int j=i-1; 6. int tmp=arr[i]; 7. while(j>=0){ 8. 9. if(arr[j]>tmp){ 10. arr[j+1]=arr[j]; 11. } 12. if(arr[j]<tmp){ 13. arr[j+1]=tmp; 14. break; 15. } 16. j--; 17. } 18. arr[j+1]=tmp; 19. } 20. }
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序：
基本思想：
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
代码实现：
1. public void shellSort(int[]arr){ 2. 3. int gap= arr.length/2; 4. 5. while(gap>=1){ 6. 7. for(int i=gap;i<arr.length;i++){ 8. int j=i-gap; 9. int tmp=arr[i]; 10. while(j>=0){ 11. 12. if(arr[j]>tmp){ 13. arr[j+gap]=arr[j]; 14. } 15. if(arr[j]<tmp){ 16. arr[j+gap]=tmp; 17. break; 18. } 19. j-=gap; 20. } 21. arr[j+gap]=tmp; 22. 23. } 24. gap/=2; 25. } 26. }
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定：
4. 稳定性：不稳定
选择排序：
选择排序过程
基本思想：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
直接选择排序:
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
选择排序
代码实现：
1. public void selectSort(int[]arr){ 2. 3. for(int i=0;i< arr.length;i++){ 4. int minIndex=i; 5. 6. int j=i+1; 7. while(j< arr.length){ 8. 9. if(arr[j]<arr[minIndex]){ 10. minIndex=j; 11. } 12. 13. j++; 14. } 15. if(minIndex!=i){ 16. swap(arr,i,minIndex); 17. } 18. 19. } 20. 21. } 22. public void swap(int[]arr,int i,int j){ 23. int temp=arr[i]; 24. arr[i]=arr[j]; 25. arr[j]=temp; 26. }
【直接选择排序的特性总结】
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
堆排序
堆排序过程
堆排序在博主的这一篇文章有详细解释：
交换排序
基本思想：
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序：
冒泡排序在博主的这一篇文章有详细解释：
【冒泡排序的特性总结】
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
快速排序：
快速排序过程
基本思想：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
快速排序
Hoare递归代码实现：
1. /** 2. * 快速排序(Hoare版) 3. * 时间复杂度：O(n*logn) 4. * 空间复杂度：O(logn) 5. * 稳定性：不稳定 6. * @param arr 7. * 问题：当我们给定的数据是有序的时候其时间复杂度为O(n^2),空间复杂度达到了O(n) 8. */ 9. public void quickSort(int[]arr){ 10. quick(arr,0,arr.length-1); 11. } 12. 13. private void quick(int[]arr,int start,int end){ 14. 15. if(start>=end){ 16. return; 17. } 18. 19. int pivot=pivotPartationHoare(arr,start,end); 20. quick(arr,start,pivot-1); 21. quick(arr,pivot+1,end); 22. } 23. //Hoare法 24. private int pivotPartationHoare(int[]arr,int left,int right){ 25. int i=left; 26. int pivot=arr[left]; 27. 28. while(left<right){ 29. 30. //left<right不能少，否则会出现越界 31. while (left<right&&arr[right]>=pivot){ 32. right--; 33. } 34. while (left<right&&arr[left]<=pivot){ 35. left++; 36. } 37. 38. //都找到后交换 39. swap(arr,left,right); 40. 41. } 42. 43. //一边找完之后和原来的left交换 44. swap(arr,left,i); 45. 46. return left;//为新的基准 47. 48. } 49. 50. public void swap(int[]arr,int i,int j){ 51. int temp=arr[i]; 52. arr[i]=arr[j]; 53. arr[j]=temp; 54. } 55.
