JAVA几种排序原理及代码实现

 

  一，直接插入排序

 

稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。

 

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

 

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中;依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

 

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。

 

直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。
插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

实现：

package com.sg.sort;

public class InsertSort {
	public static void main(String[] args) {
		// 默认数组
		int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 };
		sort(sortArr);
	}

	private static void sort(int[] sortArr) {
		int temp = 0, j = 0;
		int sortArrLength = sortArr.length;
		for (int i = 1; i < sortArrLength; i++) {
			j = i - 1;
			temp = sortArr[i];
			for(;j >= 0 && temp < sortArr[j]; j--){
				//将大于temp的值整体后移一个单位
				sortArr[j+1] = sortArr[j];
			}
			sortArr[j + 1] = temp;
		}
		for(int i = 0; i < sortArrLength; i++){
			 System.out.print(sortArr[i]+",");  
		}
	}
}

2，

package com.sg.sort;

public class InsertSort2 {

	 public static int count = 0;  
	  
	    public static void main(String[] args) {  
	  
	    	int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 }; 
	        print(sortArr);  
	        insertSort(sortArr);  
	        print(sortArr);  
	  
	    }  
	  
	    public static void insertSort(int[] sortArr) {  
	        for (int i = 1; i < sortArr.length; i++) {  
	            // 缓存i处的元素值  
	            int tmp = sortArr[i];  
	            if (sortArr[i] < sortArr[i - 1]) {  
	                int j = i - 1;  
	                // 整体后移一格  
	                while (j >= 0 && sortArr[j] > tmp) {  
	                	sortArr[j + 1] = sortArr[j];  
	                    j--;  
	                }  
	                // 最后将tmp插入合适的位置  
	                sortArr[j + 1] = tmp;  
	                print(sortArr);  
	            }  
	        }  
	    }  
	  
	    public static void print(int[] sortArr) {  
	        for (int i = 0; i < sortArr.length; i++) {  
	            System.out.print(sortArr[i] + "\t");  
	        }  
	        System.out.println();  
	    }  
}

 

二，冒泡排序

       我们把要排序的数组A = {3,4,2,1} 看成一组水泡， <!--[endif]-->就像冒泡一样，轻的在上面，重的在下面，换成数据，就是小的在上面，大的在下面。 我们先把最轻的冒出到顶端，然后冒出第二轻的在最轻的下面，接着冒出第三轻的。依次内推。直到所有都冒出来了为止。
3.我们怎么做到把最轻的放在顶端呢？我们从最底下的数据开始冒，如果比他上面的数据小，就交换（冒上去），然后再用第二第下的数据比较(此时他已经是较 轻的一个)，如果他比他上面的小，则交换，把小的冒上去。直到比到第一位置，得到的就是最轻的数据咯，这个过程就像是冒泡一样，下面的和上面的比较，小的 冒上去。大的沉下来。

 

       基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

 

代码实现：

package com.sg.sort;

public class BubbleSort {
	public static void main(String[] args) {
		// 默认数组
		int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 };
		sort(sortArr);
	}
	
	private static void sort(int[] sortArr) {
		 int temp = 0;  
		 int sortArrLength = sortArr.length;
		 
		 for(int i = 0; i < sortArrLength - 1; i++){
			 for(int j = 0; j < sortArrLength - 1 - i; j++){
				 if (sortArr[j] > sortArr[j + 1]) {
					temp = sortArr[j];
					sortArr[j] = sortArr[j + 1];
					sortArr[j + 1] = temp;
				}
			 }
		 }
		 
		 for (int i = 0; i < sortArrLength; i++) {
			 System.out.print(sortArr[i]+",");
		}
	}
	
}

2，

package com.sg.sort;

public class BubbleSort2 {

	 public static void main(String[] args) {  
		 	int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 }; 
	        print(sortArr);  
	        bubbleSort(sortArr);  
	        System.out.println("排序后的数组：");  
	        print(sortArr);  
	    }  
	  
	    public static void swap(int[] data, int i, int j) {  
	        if (i == j) {  
	            return;  
	        }  
	        data[i] = data[i] + data[j];  
	        data[j] = data[i] - data[j];  
	        data[i] = data[i] - data[j];  
	    }  
	  
	    public static void bubbleSort(int[] data) {  
	        for (int i = 0; i < data.length - 1; i++) {  
	            // 记录某趟是否发生交换，若为false表示数组已处于有序状态  
	            boolean isSorted = false;  
	            for (int j = 0; j < data.length - i - 1; j++) {  
	                if (data[j] > data[j + 1]) {  
	                    swap(data, j, j + 1);  
	                    isSorted = true;  
	                    print(data);  
	                }  
	            }  
	            if (!isSorted) {  
	                // 若数组已处于有序状态，结束循环  
	                break;  
	            }  
	        }  
	    }  
	  
	    public static void print(int[] data) {  
	        for (int i = 0; i < data.length; i++) {  
	            System.out.print(data[i] + "\t");  
	        }  
	        System.out.println();  
	    }  

}

 

 

三，简单选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。

基本思想：
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，
使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。…… ③
第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，
使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循环之前,
将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的
元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,
有比当前外层循环位置更小的元素,需要将这两个元素交换.

 

总结：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；

然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

 

代码实现：

package com.sg.sort;

public class SelectSort {
	public static void main(String[] args) {
		// 默认数组
		int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 };
		sort(sortArr);
	}
	
	private static void sort(int[] sortArr) {
		 int temp= 0,position = 0,j = 0;  
		 int sortArrLength = sortArr.length;
		 
		 for(int i = 0; i < sortArrLength; i++){
			 j = i + 1;
			 position = i;
			 temp = sortArr[i];
			 for(; j < sortArrLength; j++){
				 if(sortArr[j] < temp){
					 temp = sortArr[j];
					 position = j;
				 }
			 }
			 sortArr[position] = sortArr[i];
			 sortArr[i] = temp;
		 }
		 for (int i = 0; i < sortArrLength; i++) {
			System.out.print(sortArr[i]+",");
		}
	}
}

 四，快速排序

 

快速排序是一个速度非常快的交换排序算法，它的基本思路很简单，从待排的数据序列中任取一个数据（如第一个数据）作为分界值，所有比它小的数据元素放到左 边，所有比它大的数据元素放到它的右边。经过这样一趟下来，该序列形成左右两个子序列，左边序列中的数据元素的值都比分界值小，右边序列中数据元素的值都 比分界值大。
接下来对左右两个子序列进行递归排序，对两个子序列重新选择中心元素并依此规则调整，直到每个元素子表的元素只剩下一个元素，排序完成。

思路：
1.定义一个i变量，i变量从左边第一个索引开始，找大于分界值的元素的索引，并用i来记录它。
2.定义一个j变量，j变量从右边第一个索引开始，找小于分界值的元素的索引，并用j来记录它。
3.如果i<j，交换i,j两个索引处的元素。
重复执行以上1,2,3步，直到i>=j，可以判断j左边的数据元素都小于分界值，j右边的数据元素都大于分界值，最后将分界值和j索引处的元素交换即可。

时间复杂度
最好情况（每次总是选到中间值作枢轴）T(n)=O(nlogn)
最坏情况（每次总是选到最小或最大元素作枢轴）
做n-1趟，每趟比较n-i次，总的比较次数最大：[O(n²)]
平均时间复杂度为：：T(n)=O(nlogn)

代码实现：

package com.sg.sort;

public class QuickSort {
	public static void main(String[] args) {
		// 默认数组
		int[] sortArr = { 51, 31, 5, 90, 46, 78, 1, 63, 99, 10 };
		print(sortArr);  
        quickSort(sortArr, 0, sortArr.length - 1);  
        System.out.println("排序后的数组：");  
        print(sortArr);  
	}

	public static void quickSort(int[] sortArr, int start, int end) {
		if (start >= end)
			return;
		// 以起始索引为分界点
		int pivot = sortArr[start];
		int i = start + 1;
		int j = end;
		while (true) {
			while (i <= end && sortArr[i] < pivot) {
				i++;
			}
			while (j > start && sortArr[j] > pivot) {
				j--;
			}
			if (i < j) {
				swap(sortArr, i, j);
			} else {
				break;
			}
		}
		// 交换 j和分界点的值
		swap(sortArr, start, j);
		print(sortArr);
		// 递归左子序列
		quickSort(sortArr, start, j - 1);
		// 递归右子序列
		quickSort(sortArr, j + 1, end);
	}

	//
	public static void swap(int[] sortArr, int i, int j) {
		if (i == j) {
			return;
		}
		sortArr[i] = sortArr[i] + sortArr[j];
		sortArr[j] = sortArr[i] - sortArr[j];
		sortArr[i] = sortArr[i] - sortArr[j];
	}

	public static void print(int[] sortArr) {
		for (int i = 0; i < sortArr.length; i++) {
			System.out.print(sortArr[i] + "\t");
		}
		System.out.println();
	}
}