|
排序算法是数据结构中十分基础的内容，本文总结了常用的排序算法的原理和性能，还给出了相关的图解，并且采用java语言实现了算法，最后给了一个面试中实际的例子，以及算法复杂度的比较
1、选择排序
最基本的排序算法，原理看图就可以理解： 
// 选择排序
public int[] selectsort(int[] arr)
{
for(int x=0;x0 && arr[j] arr[j+1]) { // 相邻元素两两对比
int temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
4、快速排序
  
/**
* 将数组的某一段元素进行划分，小的在左边，大的在右边
*/
public static int divide(int[] a, int start, int end){
//每次都以最右边的元素作为基准值
int base = a[end];
//start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。
while(start < end){
while(start < end && a[start] = base)
//从右边开始遍历，如果比基准值大，就继续向左走
end--;
//上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换
if(start < end){
//交换
int temp = a[start];
a[start] = a[end];
a[end] = temp;
//交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位
start++;
}
}
//这里返回start或者end皆可，此时的start和end都为基准值所在的位置
return end;
}
/**
* 排序
*/
public static void sort(int[] a, int start, int end){
if(start > end){
//如果只有一个元素，就不用再排下去了
return;
}
else{
//如果不止一个元素，继续划分两边递归排序下去
int partition = divide(a, start, end);
sort(a, start, partition-1);
sort(a, partition+1, end);
}
}
5、归并排序
  治的最后过程举例   
package cn;
import java.util.Arrays;
// 归并排序
public class MergeSort {
public static void main(String []args)
{
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr,0,8);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr,int start,int end)
{
if(start1,4,2,7,9,8,3,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int [] arr)
{
//确定初始的增量gap，保证其不能越界
int gap=1;
while(gap=1)
{
for(int i=gap;i=gap && arr[j] |