1.排序分为以下四类共七种排序方法：
交换排序：
1) 冒泡排序
2) 快速排序
选择排序：
3) 直接选择排序
4) 堆排序
插入排序：
5) 直接插入排序
6) 希尔排序
合并排序：
7) 合并排序
2.冒泡排序
时间复杂度O(n2)
其基本思想是：通过相邻元素之间的比较和交换，使关键字较小的元素逐渐从底部移向顶部，就像水底下的气泡一样逐渐向上冒泡.
public class BubbleSort {
public static void bubbleSort(int [] arr){
if(arr==null||arr.length==0){
return;
}
for(int i=0;i<arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){//从后向前冒泡，把小的元素冒到前面去
if(arr[j]<arr[j-1]){
swap(arr,j-1,j);
}
}
}
}
public static void swap(int [] arr,int m,int n){
int temp=arr[m];
arr[m]=arr[n];
arr[n]=temp;
}
public static void main(String[] args) {
int [] arr=new int[9];
arr[0]=9;
arr[1]=1;
arr[2]=5;
arr[3]=8;
arr[4]=3;
arr[5]=7;
arr[6]=4;
arr[7]=6;
arr[8]=2;
System.out.print("[");
for (int num : arr) {
System.out.print(num+" ");
}
System.out.print("]");
System.out.println();
BubbleSort.bubbleSort(arr);
System.out.print("[");
for (int num : arr) {
System.out.print(num+" ");
}
System.out.print("]");
System.out.println();
}
}
3.快速排序
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
快速排序的思想：冒泡+二分+递归分治
什么叫递归分治？
基本思想就是：将原问题分解为若干个规模更小的但结构与原问题相似的子问题，递归地解决这些子问题，然后将这些子问题的解组合为原问题的解。
public class Test{
//划分
public static int Division(int[] arr,int left,int right){
int base=arr[left]; //把左边的第一个数作为基准
while(left<right){
while(left<right && arr[right]>base)
--right; //从右向左遍历找第一个比基准小的元素
arr[left]=arr[right]; //找到之后就把左边和右边互换一下
while(left<right && arr[left]<base)
++left; //从左向右遍历找第一个比基准元素小的元素
arr[right]=arr[left]; //找到之后，把刚才从右向左遍历得到的arr[left]和现在的arr[right]互换
}
arr[left]=base;
return left;
}
public static void QuickSort(int[] arr,int left,int right){
int i;
if(left<right){
i=Division(arr,left,right); //分割
QuickSort(arr,left,i-1); //将两部分分别排序
QuickSort(arr,i+1,right);
}
}
public static void main(String[] args){
int[] arr={4,2,1,6,0,-5,1};
int i;
QuickSort(arr,0,arr.length-1);
for(i=0;i<7;i++)
System.out.print(arr[i]);
}
}
栗子：线性表的长度为10，在最坏情况下，冒泡排序需要比较次数为（45）
最坏的情况即是每个元素两两都要相比较
所以应该是9+8+7...+1=45