简单选择排序

思路：选出最小的元素，放在第一个位置，之后在剩下的元素中，选出最小的元素，放在第二个位置.........以此类推，直到完成排序。

package h;public class MyA {  static void selectOne(int[] a, int begin)  {    int p = begin; //假设修正法     for(int i=begin+1; i<a.length; i++){      if(a[i] < a[p]) p = i;  //记录最小元素所在位置    }      {int tmp = a[p]; a[p] = a[begin]; a[begin] = tmp; }  //交换元素  }   static void show(int[] a) {  for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");  System.out.println(); }  public static void main(String[] args)  {    int[] a = {12,8,3,5,16,22,9,14,2,17};    show(a);      for(int k=0; k<a.length-1; k++){     selectOne(a, k);     show(a);    }   }}

插入排序

思路：把新元素加到已经有序的队列中

public class MyA{	// 第k项插入到前边的序列中	static void insertOne(int[] a, int k)	{		for(int i=0; i<=k; i++){			if(a[i]>=a[k]){ //找到了插入的位置				int tmp = a[k];				for(int j=k-1; j>=i; j--) a[j+1] = a[j];				a[i] = tmp;				break;  			}		}	}		static void show(int[] a)	{		for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");		System.out.println();	}		public static void main(String[] args)	{		int[] a = {15,22,13,9,16,23,18,4,33,25,14};		show(a);				for(int i=1; i<a.length; i++){			insertOne(a,i);			show(a);		}	}}

快速排序

思路：以一个元素作为标尺，将数据分成两块，一块是小于标尺元素大小的，另一块是大于等于标尺元素大小的。之后再进行递归，

将刚才分成的两块按照之前的方法再次进行快速排序，直到改分区（块）内没有需要排序的元素。

package j;class MyA{	static void show(int[] a)	{		for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");		System.out.println();	}		static void quickSort(int[] a, int begin, int end)	{		if(end-begin<=1) return;				int x = a[begin];  // 标尺		int p1 = begin;		int p2 = end;		boolean dr = true;  // 比较方向 一次左一次右		L1:	while(p1<p2){			if(dr){				for(int i=p2; i>p1; i--){					if(a[i] <= x){						a[p1++] = a[i];						p2 = i;						dr = !dr;						continue L1;					}				}				p2 = p1;			}			else{				for(int i=p1; i<p2; i++){					if(a[i] >= x){						a[p2--] = a[i];						p1 = i;						dr = !dr;						continue L1;					}				}				p1 = p2;			}		}		a[p1] = x;				quickSort(a,begin,p1-1);		quickSort(a,p1+1,end);	}			public static void main(String[] args)	{		int[] a = {15,22,13,9,16,33,15,23,18,4,33,25,14};		show(a);				quickSort(a, 0, a.length-1);		show(a);	}}

希尔排序

思路：由于原始数据的有序性对排序时间的长短很一定的影响，按一定的步长对数据进行分组，使用插入排序法进行排序。之后不断的降低步长，直到步长为1。

public class MyA{	//希尔排序之一趟排序, dk 为步长	static void shellOne(int[] data, int dk)	{		for(int k=0; k<dk;k++){			//子组做简单插入排序			for(int i=1; k+i*dk<data.length; i++){				//确定插入位置				for(int j=0; j<=i; j++){					if(data[k+j*dk] >= data[k+i*dk]){						int tmp = data[k+i*dk];						for(int p=i-1; p>=j;p--) data[k+(p+1)*dk] = data[k+p*dk];						data[k+j*dk] = tmp;						break;					}				}			}		}	}		static void show(int[] data)	{		for(int i=0; i<data.length; i++) System.out.print(data[i] + " ");		System.out.println();	}		public static void main(String[] args)	{		int[] a = {49,38,65,97,76,13,27,49,55,4};		show(a);				shellOne(a,5);		show(a);		shellOne(a,3);		show(a);		shellOne(a,1);		show(a);	}}