1.冒泡排序
(1)方法描述：
冒泡排序(bubble sort)是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
(2)算法原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
(3)算法评价
时间复杂度：最好的情况(全部正序)---比较次数n-1
---移动次数0
最坏的情况(全部正序)---比较次数1/2 ( n*n - n )
---移动次数3/2 ( n*n - n )
空间复杂度：S(n)=O(1)
代码实现：下列三种排序的公共代码：
public void swap(int a[],int i,int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp; } public void print(int[] a){ for(int x:a){ System.out.print(x+" "); } System.out.println(); } 冒泡排序代码实现：
1.普通冒泡排序
@Test public void bubbleSort(){ int a[]={1,0,-1,13,4,7,13,49}; print(a); for(int i=0;i<a.length-1;i++){//当只剩最后一个元素时，不需要在冒泡 for(int j=0;j<a.length-i-1;j++){ //j:0~n-i+1 if(a[j]>a[j+1]){ swap(a, j, j+1); } } } print(a); }2：优化后冒泡排序
@Test public void bubbleSort_2(){ int a[]={1,0,-1,13,4,7,13,49}; print(a); for(int i=0;i<a.length-1;i++){//当只剩最后一个元素时，不需要在冒泡 boolean boo=true; for(int j=0;j<a.length-i-1;j++){ //j:0~n-i+1 if(a[j]>a[j+1]){ boo=false; swap(a, j, j+1); } } if(boo){ //如果进行一趟比较之后，没有交换位置，说明每一个位置都满足a[j]<a[j+1]，则整个序列有序 break; } } print(a); } 2： 选择排序 (1)方法描述
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
(2)算法原理
1：通过n-1次比较，从n个数中找出最小的， 将它与第一个数交换——第一趟选择排序，结果最小的数被安置在第一个元素位置上。 2：通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换——第二趟选择排序。 3：重复上述过程，共经过n-1趟排序后，排序结束。
(3)算法评价
时间复杂度： 最好的情况(全部正序)---比较次数1/2 (n² - n )
---移动次数0
最坏的情况(全部正序)---比较次数1/2 ( n² - n )
---移动次数3 ( n - 1 )
空间复杂度：S(n)=O(1)
相对于冒泡算法，选择排序更优
代码实现：
@Test public void selectSort_2(){ int a[]={1,0,-1,13,4,7,13,49}; print(a); for(int i=0;i<a.length-1;i++){ int k=i; for(int j=i+1;j<a.length;j++){ //从i+1位置开始往后查找，如果有比当前位置的数小的数，则记录那个小数的位置 if(a[k]>a[j]){ k=j; } } //进行一趟查找后，k记录的是最小数的下标 if(k!=i){ swap(a, i, k); } } print(a); }
3： 插入排序
插入排序：1:直插入排序
2:二分插入排序(在直接插入排序的基础上，利用二分(折半)查找算法决策出当前元素所要插入的位置。)
(1)方法描述
插入排序(insert sort)就是每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
(2)算法原理
记录存放在数组R[0….n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[0…i-1]和R[i….n-1]，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。 将当前无序区的第1个记录R[i]插入到有序区R[0….i-1]中适当的位置，使R[0…i]变为新的有序区。
(3)算法分析
插入排序是一个稳定的排序方法。
最好情况下, 排序前记录已按关键字从小到大有序, 每趟只需与前面有序记录序列的最后一个记录比较1次, 移动2次记录,
总的关键字比较次数为 n-1, 记录移动次数为 2(n-1)。
在平均情况下的关键字比较次数和记录移动次数约为n² /4。
空间复杂度：S(n)=O(1) (4)二分查找
二分查找：找到中间元素，如果中间元素比当前元素大，则当前元素要插入到中间元素的左侧；否则，中间元素比当前元素小，则当前元素要插入到中间元素的右侧。
代码实现：
@Test public void insertSort(){ int a[]={1,0,-1,13,4,7,13,49,31,21,3}; print(a); //依次把每个数插入到有序序列中 for(int i=0;i<a.length-1;i++){ //i+1表示待插入的数的下标 所以循环执行到a.length-1 //temp表示待插入数 int temp=a[i+1]; //j表示前j个数有序 int j=i; /* * 下面一段代码表示：从最后一个有序位置往前查找， * 若待插入数，比位置j的数小，则把位置j的数往后挪 * 直到j<0超出了左边界，或者待插入数比位置j的数大，则把待插入数放在j+1位置 */ while(temp<a[j]){ a[j+1]=a[j]; j--; if(j<0){ break; } } a[j+1]=temp; } print(a); } //带二分的插入排序 //★二分必须有序,如果有序可以考虑二分 @Test public void insertSort_2(){ int a[]={1,0,-1,13,4,7,13,49,31,21,3}; print(a); //(0,i)区间的数是有序的 for(int i=0;i<a.length-1;i++){ //待插入数 int temp=a[i+1]; //二分法查找，插入位置，high+1 int low=0; int high=i; // int mid=(low+high)/2; 这样做mid一直没变，会错 int mid; while(low<=high){ mid=(low+high)/2; //只有当high到low的左边时，此时待插入数的位置为high+1 if(temp>a[mid]){ //待插入数比中间位置的数大，则位于右区间 //因为待插入数比mid位置的数大，所以可以使下一次的最低位为mid+1 low=mid+1; }else{ //待插入数比中间位置的数小，则位于左区间 //因为待插入数比mid位置的数小或者等于，所以可以使下一次的最高位为mid-1 high=mid-1; } } //循环结束后high将位于low的左边，high+1即为待插入数的位置 //把high+1后面的数全部往后挪一位，空出位置给待插入数 //此处应该注意，要从有序的最后一位(i位置)开始挪，不然值会覆盖, for(int j=i;j>high;j--){ a[j+1]=a[j]; } //把待插入数放在腾出来的high+1位置 a[high+1]=temp; } print(a); }
插入排序是一个稳定的排序方法。
