黑马程序员--Java简单排序算法

------- android培训、java培训、期待与您交流！ ----------

Java简单排序算法

最简单的排序方法：直接选择排序、冒泡排序。

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

直接选择排序：

（1）关键字比较次数

无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n(n-1)/2=0(n2)

（2）记录的移动次数

当初始文件为正序时，移动次数为0

文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。

直接选择排序的平均时间复杂度为O(n2)。

 

 

class SelectionSort
{
	public static void main(String[] args)
	{
		double[] arr = new double[10000];
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=(arr.length*Math.random());
		}
		//排序前时间
		long st1 = System.currentTimeMillis();
		//排序
		sort(arr);
		//排序后时间
		long st2 = System.currentTimeMillis();
		for(int i=0;i<arr.length;i++)
		{
			System.out.print(arr[i]+" ");
		}
		System.out.println("");
		System.out.println("共花费"+(st2-st1)+"毫秒");
	}
	
	public static void sort(double[] a)
	{
		int sortedLen= a.length;
		for(int i=0;i<sortedLen-1;i++)
		{
			for(int j=i+1;j<sortedLen;j++)
			{
				if(a[i]>a[j])
				{
					swap(a,i,j);
				}
			}
		}
	}
	public static void swap(double[] arr,int a,int b){
			double temp = arr[a];
			arr[a] = arr[b]; 
			arr[b] = temp;	
	}

}

 

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。

冒泡排序：

（1）算法的最好时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：

Cmin=n-1

Mmin=0。

冒泡排序最好的时间复杂度为O(n)。

（2）算法的最坏时间复杂度

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序的最坏时间复杂度为O(n2)。

（3）算法的平均时间复杂度为O(n2)

虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。

class BubbleSort {
	public static void main(String[] args) {
		double[] arr = new double[10000];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (arr.length * Math.random());
		}
		// 排序前时间
		long st1 = System.currentTimeMillis();
		// 排序
		sort(arr);
		// 排序后时间
		long st2 = System.currentTimeMillis();
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println("");
		System.out.println("共花费" + (st2 - st1) + "毫秒");
	}

	public static void sort(double[] a) {
		int sortedLen = a.length;
		for (int i = 0; i < sortedLen - 1; i++) {
			for (int j = 0; j < sortedLen - i - 1; j++) {
				if (a[j] > a[j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
	}

	public static void swap(double[] arr, int a, int b) {
		double temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}