常用排序技术详细总结（1）
一、插入排序
1.直接插入排序
1.1基本思想：依次将待排序序列中的每个记录插入到一个已排好序的序列中，直到全部记录都排好序。
1.2具体排序过程：（1）将整个待排序的记录序列划分为有序区和无序区，初始化有序去区为待排序记录序列中的第一个 记录，无序区包括所有剩余待排序的记录；
（2）将无序区的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一 个记 录；
（3）重复执行（2），直到无序区中没有记录为止。
1.3算法：
public static void insertSort(int r[],int n){
int i;
int j;
for(i = 2; i <= n; i++){ //循环无序区的记录
r[0] = r[i]; //设置哨兵
for(j = i - 1; r[0] < r[j]; j--){ //循环有序区，并且从有序区后面往前循环查找要插入的位置
r[j+1] = r[j]; //满足r[0] < r[i] 时，有序区记录逐个往后移动。
}
r[j+1] = r[0]; //将数据插入到正确的地方
}
}
public static void printArr(int[] numbers)
{
for(int i = 1 ; i < numbers.length ; i ++ )
{
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
public static void main(String[] args) {
int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
System.out.print("排序前：");
printArr(numbers);
insertSort(numbers,9);
System.out.println("插入排序后：");
printArr(numbers);
}1.4算法分析与注意：
1.4.1最好情况下，待排序序列为正序，每趟只需与有序序列的最后一个记录的关键码比较一次，移动两个记录，时间复杂度为O(n).
1.4.2最坏情况下，待排序为逆序。在第i趟插入时，第i个记录必须与前面i-1个记录的关键码及哨兵作比较，并且每比较一次就要做一次记录的移动，所以时间复杂度为O(n2);(n的平方)
平均情况下时间复杂度为O(n2);（n的平方）。
注意：算法简单容易实现，当序列中的记录基本有序或待排序记录较少时，他是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。
2.希尔排序
2.1基本思路：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。
2.2具体排序过程：假设待排序的记录为n个，先去参数d<n，例如，取d=n/2,如n=4,d=2;n=5,d=2;将所有相距为d的记录构成一组，从而将整个待排序记录序列分隔成d个子序列。对每个子序列分别进行直接插入排序，然后再缩小间隔d。取d=d/2,重复上述分隔，再对每个子序列分别进行直接插入排序，直到最后取d=1,即将所有记录放在一组进行一次直接插入排序，最终将所有记录重新排列成按关键码有序的序列。
2.3算法：
public static void shellSort(int r[],int n){
int i,j,d;
for(d = n/2;d >= n;d = d/2){ //以增量为d进行直接插入排序
for(i= d+1;i <= n; i++){ //将r[i]插入到所属的子列中
r[0] = r[i]; //暂存带插入记录
for(j = i - d; j >0 && r[0] < r[j]; j=j-d){
r[j+d] = r[j]; //记录后移d个位置
}
r[j+d] = r[0];
}
}
}
public static void printArr(int[] numbers)
{
for(int i = 0 ; i < numbers.length ; i ++ )
{
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
public static void main(String[] args) {
int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
System.out.print("排序前：");
printArr(numbers);
shellSort(numbers,9);
System.out.println("希尔排序后：");
printArr(numbers);
}2.4性能与注意
希尔排序的时间性能在O(n2)和O(nlog2n)之间，当n在某个特定范围时，希尔排序的时间性能约为O(n1.3).
二、交换排序
1起泡排序
1.1基本思路：两两比较相邻记录的关键码，如果反序就交换，知道没有反序为止。
1.2具体排序过程；
1.将整个待排序的记录序列划分成有序区和无序区，初始化有序区为空，无序区包括所有待排序的记录。
2.对无序区从前向后依次将相邻记录的关键码进行比较，若反序则交换，从而使得关键码小的记录向前移，关键码大的记录向后移。
3.重复执行2操作，直到无序区中没有反序的记录。
1.3算法：
public static void bulleSort(int r[],int n){
int exchange = n;
int temp;
while(exchange != 0){
int bound = exchange;
exchange = 0;
for(int j = 0;j < bound; j++){
if(r[j] > r[j+1]){
temp = r[j];
r[j] = r[j+1];
r[j+1] = temp;
exchange = j;
}
}
}
}
public static void printArr(int[] numbers)
{
for(int i = 0 ; i < numbers.length ; i ++ )
{
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
public static void main(String[] args) {
int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
System.out.print("排序前：");
printArr(numbers);
bulleSort(numbers,9);
System.out.println("起泡排序后；");
printArr(numbers);
}1.4性能分析
在最好的情况下，待排序记录序列为正序，算法只执行一趟，进行了n-1次关键码的比较，不需要移动记录，时间复杂度为O(n);
在最坏的情况下，待排序记录序列为反序，时间复杂度为O(n2);
2快速排序
2.1基本思路：首先选择一个轴值(povit)，将待排序记录划分成独立的两个部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。
一次划分算法：
public static int partition(int r[],int first,int end){
int i = first;
int j = end;
int temp1;
int temp2;
while(i < j){
while(i < j && r[i] <= r[j]){
j--;
}
if(i<j){
temp1 = r[i];
r[i] = r[j];
r[j] = temp1;
i++;
}
while(i < j && r[i] <= r[j]){
i++;
}
if(i < j){
temp2 = r[j];
r[j] = r[i];
r[i] = temp2;
j--;
}
}
return i;
}
/**
* 递归算法
* @param r
* @param first
* @param end
*/
public static void QuickSort(int r[],int first,int end){
int pivot;
if(first < end){
pivot = partition(r, first, end);
QuickSort(r, first, pivot - 1);
QuickSort(r, pivot + 1, end);
}
}
public static void printArr(int[] numbers)
{
for(int i = 0 ; i < numbers.length ; i ++ )
{
System.out.print(numbers[i] + ",");
}
System.out.println("");
}
public static void main(String[] args) {
int[] numbers = {10,20,15,0,6,7,2,1,-5,55};
System.out.print("排序前：");
printArr(numbers);
QuickSort(numbers,0,9);
System.out.println("快速排序后；");
printArr(numbers);
}性能分析：在最好情况下，O(log2n),最坏情况下，O(n),平均情况下，O(log2n).
快速排序适用于待排序记录个数很大且原始记录随机排列的情况。快速排序的平均性能是迄今为止所有内排序算法中最好的一种。