用Java实现 一些面试要求的基本的排序算法

首先是插入排序：

个人思路：插入排序就是将一个无序的数组，从第一个开始，将下一个数插入到前面的有序数组中，使之前的数组依然有序。（我说的比较白话，因为是自己总结的）

比如数组 {1,5,3,4,5,8,2}，从第二个开始，跟前面的数比较，如果小于前面的数，则交换。所以步骤如下：

{1,5,3,4,5,8,2}-->{1,3,5,4,5,8,2}-->{1,3,4,5,8,2}-->{1,3,4,5,8,2}-->{1,3,4,5,2,8}-->{1,3,4,2,5,8}-->{1,3,2,4,5,8}-->{1,2,3,4,5,8}，最后排序完成。

算法实现为：

public class InsertSort {
	public static void main(String []args){
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		insertSort(a);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	public static void insertSort(int []a){
		//从第二位开始
		for(int i=1;i<a.length;i++){
			//判断j是否大于零，这样避免a[j-1]越界
			//从i开始，依次找前面的数，如果a[j]<a[j-1]（后面的数大于前面的数），
			//则做交换，并且j--。 如果a[j]>a[j-1]，则说明已经到了正确的位置，结束for循环
			for(int j=i;j>0&&(a[j]<a[j-1]);j--){
				int temp = a[j];
				a[j] = a[j-1];
				a[j-1] = temp;
			}
		}
	}
}

希尔排序：希尔排序是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。算法实现如下：

public class ShellSort {
	public static void main(String[] args) {
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		shellSort(a);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	public static void shellSort(int a[]){
		//i是增量的值
		for(int i=a.length/2;i>2;i/=2){
			//将前i个属于总量为i的不同分组做插入排序
			for(int j=0;j<i;j++){
				insertSort(a,j,i);
			}
		}
		insertSort(a,0,1);
	}
	public static void insertSort(int a[],int start,int inc){
		//从start开始没意义，所以从第二个属于inc增量的组的开始算
		for(int i=start+inc;i<a.length;i+=inc){
			//用插入排序对其进行排序  当j>=inc时，是因为最小j就为inc，如果比inc还小，则会越界
			for(int j=i;j>=inc&&(a[j]<a[j-inc]);j-=inc){
				int temp = a[j];
				a[j] = a[j-inc];
				a[j-inc] = temp;
			}
		}
	}
}

堆排序： 堆排序是用数组来表示一个完全二叉树。 具体思路就不写了，在算法代码中我直接用注释说明，原理大家找下资料就可以了

public class HeapSort {
	//本人用的是大根堆
	public static void main(String[] args) {
		int a[] = {1,5,3,4,5,8,10,21,4,50,100,5,1};
		heapSort(a);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	//moveDown主要是用来将子树初始化，first相当于当前子树的根，last是最后一个节点的位置
	public static void moveDown(int a[],int first,int last){
		//得到左子树   因为数组是从零开始，所以需要加一
		int largest = 2*first+1;
		while(largest<=last){//largest可以等于largest因为最后一位也可能是最大值，不能去除
			//这个循环是为了找到最大节点的位置
			//largest记录着当前最大节点的位置
			while(largest<last&&(a[largest]<a[largest+1])) largest++;
			//找到最大的位置，判断是否比first处的值大，大的话，交换值，同时因为移动了子树的节点
			//largest为根的子树的堆混乱了，需要重新建堆，所以将根first设为largest
			//largest依旧取根的左子树
			//如果小的话，则说明根处的值已经是最大的了，跳出循环
			if(a[first]<a[largest]){
				int temp = a[first];
				a[first] = a[largest];
				a[largest] = temp;
				first = largest;
				largest = 2*first+1;
			}else{
				largest = last+1;
			}
		}
	}
	public static void heapSort(int a[]){
		//i=a.length/2-1，得到最后一个叶子节点的父亲，从最后的一个子树开始进行建堆
		for(int i=a.length/2-1;i>=0;i--){
			moveDown(a,i,a.length-1);
		}
		//从最后一个开始，依次将最大的数交换到最后，
		for(int i=a.length-1;i>0;i--){
			int temp = a[0];
			a[0] = a[i];
			a[i] = temp;
			//然后在将堆重新构造
			moveDown(a,0,i-1);
		}
	}
}

冒泡排序：最基本的排序，基本上大家都会0 0，就是依次选第i位（i<n），并从后面开始，将i后的最小的数冒到第i位。

算法实现：

public class maopao {
	public static void main(String []args){
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		mao(a);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	public static void mao(int a[]){
		//i从0开始
		for(int i=0;i<a.length;i++){
			//从最后一位开始，如果小于前面的数，则交换
			for(int j=a.length-1;j>i;j--){
				if(a[j]<a[j-1]){
					int temp = a[j];
					a[j] = a[j-1];
					a[j-1] = temp;
				}
			}
		}
	}
}

选择排序：

数组从i（0<i<n）开始，需要一个辅助数据，temp，存储i之后的最小的数的位置，如果选择之后，temp！=i，则交换temp和i的数，i++；

算法如下：

public class SelectSort {
	public static void main(String []args){
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		selectSort(a);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	public static void selectSort(int a[]){
		//存储当前最小的数的位置
		int temp;
		for(int i=0;i<a.length;i++){
			//temp刚开始为i
			temp = i;
			for(int j=i+1;j<a.length;j++){
				//如果存在比他小的数，则temp=j
				if(a[temp]>a[j]){
					temp = j;
				}
			}
			//如果temp！=i，说明后面有比i位上的数更小的数
			//交换temp和i位的数
			if(temp!=i){
				int t = a[i];
				a[i] = a[temp];
				a[temp] = t;
			}
		}
	}
}

快排： 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

算法如下：

public class quickSort {
	public static void main(String[] args) {
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		quickSort(a,0,a.length-1);
		for(int i =0;i<a.length;i++){
			System.out.print(a[i]+"   ");
		}
	}
	//得到中间位置，这个位置的前面的数都小于他，后面的数都大于他
	public static int partition(int a[],int low,int high){
		//以low处为基准点
		int paior = a[low];
		while(low<high){
			//从后看，如果high大于等于基准点，则high--
			while(low<high&&a[high]>=paior) high--;
			//这个时候high处的值小于等于基准点，将值付给low
			a[low] = a[high];
			//从前面看，如果low小于基准点的值，则low++
			while(low<high&&a[low]<=paior) low++;
			//这个时候low处的值大于等于基准点，将值付给high
			a[high] = a[low];
		}
		//最后将low处附上基准点的值，low就是基准点的位置，返回low
		a[low] = paior;
		return low;
	}
	public static void quickSort(int a[],int low,int high){
		if(low<high){
			//找到基准点
			int part = partition(a, low, high);
			//将基准点前面的数在做排序
			quickSort(a, low, part-1);
			//将基准点后面的数在做排序
			quickSort(a, part+1,high);
		}
	}
}

算法如下：

public class MergeSort {
	public static void main(String[] args) {
		int a[] = {1,5,3,4,5,8,10,21,4,5,1};
		int b[] = new int[a.length];
		mergeSort(a,b,0,a.length-1);
		for(int i =0;i<b.length;i++){
			System.out.print(b[i]+"   ");
		}
	}
	//合并 a的low到mid的有序数组，和mid到high的有序数组，合并成b
	public static void merge(int a[],int b[],int low,int mid,int high){
		int i = low,j=mid+1,k=low;
		while(i<=mid&&j<=high){
			if(a[i]<a[j]) b[k++] = a[i++];
			else b[k++] = a[j++];
		}
		while(i<=mid){
			b[k++] = a[i++];
		}
		while(j<=high){
			b[k++] = a[j++];
		}
	}
	public static void mergeSort(int a[],int b[],int low,int high){
		//s是中间数组
		int s[] = new int[a.length];
		if(low==high) b[low] = a[low];
		else{
			int mid = (low+high)/2;
			mergeSort(a,s,low,mid);
			mergeSort(a,s,mid+1,high);
			merge(s,b,low,mid,high);
		}
	}

}

本文章是我这两天看过总结的java代码，有些话说的太白了，可能不易于理解，请大家见谅。

用Java实现 一些面试要求的基本的排序算法,古老的榕树,5-wow.com