冒泡排序、插入排序、选择排序
希尔排序
归并排序
快速排序
排序原理图解排序过程代码的实现代码实现的API分组原理拆分原理图解代码实现
时间复杂度分析
快速排序是对冒泡排序的一种改进，他的思路是：通过一趟将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序原理
首先设定一个分界值（一般将待排序数字的第一个作为分界值）通过该分界值将数组分成左右两部分。将大于或等于分界值的数据放到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。然后，左边右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值，右侧的数组数据也可以做类似处理。重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，在递归排好右侧部分的顺序。当左侧和右侧两部分的数据排完序后，整个数组的排序也就完成了。
图解排序过程
{6,1,2,7,9,3,4,5,8}
代码的实现
代码实现的API
public static boolean greater( int a,int b) 比较两个数之间的大小public static void exch(int[] a,int i,int j) 交换索引i处与索引j处的值public static void sort(int[] a) 对数组a进行排序public static void sort(int[] a,int lo,int hi) 对数组a从索引lo到索引hi进行排序public static int partition(int[] a,int lo,int hi) 对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引下标
分组原理
把一个数组分成两个数组的基本思想：
找一个基准值（一般找数组的第一个元素），用两个指针分别指向数组的头部和尾部。先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置。再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置。交换当前左指针位置和右指针位置的元素。重复2、3、4步骤，直到左边指针的值大于右边指针的值停止。
拆分原理图解
代码实现
import java
.util
.Arrays
;
public class SortQuick {
public static void main(String
[] args
) {
int[] array
=new int[]{8,4,5,7,1,3,6,2};
sort(array
);
System
. out
. println(Arrays
. toString(array
));
}
public static boolean greater( int a
,int b
){
return a
>b
;
}
public static void exch(int[] a
,int i
,int j
){
int temp
=a
[i
];
a
[i
]=a
[j
];
a
[j
]=temp
;
}
public static void sort(int[] a
){
int lo
=0;
int hi
=a
.length
-1;
sort(a
,lo
,hi
);
}
public static void sort(int[] a
,int lo
,int hi
){
if(hi
<=lo
){
return;
}
int partition
=partition(a
,lo
,hi
);
sort(a
,lo
,partition
);
sort(a
,partition
+1,hi
);
}
public static int partition(int[] a
,int lo
,int hi
){
int key
=a
[lo
];
int left
=lo
;
int right
=hi
+1;
while(true){
while(greater(a
[--right
], key
)){
if(right
==lo
){
break;
}
}
while(greater(key
,a
[++left
])){
if(left
==hi
){
break ;
}
}
if(left
>=right
){
break ;
}else{
exch(a
,left
, right
);
}
}
exch(a
,lo
,right
);
return right
;
}
}
时间复杂度分析
