排序算法的实现与设计

Question

 

Answer 1

各种排序算法的Java实现和性能对比

• 准备工作
• 1.简单选择排序
• 2.直接插入排序
• 3.冒泡排序
• 4.快速排序
• 5.归并排序
• 6.希尔排序
• 7.堆排序
• 以上排序算法性能对比

 

准备工作

待排序数组：arr：[3,7,4,2,6]
数组元素交换函数：

//交换数组中两个位置上的元素
	public void swap(int[] arr,int i,int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}

格式化打印数组的函数：

	//打印数组,以[a1,a2,...an]格式打印
	public static void print(int[] arr) {
		System.out.print("[");
		for(int i=0;i<arr.length;i++) {
			if(i!=arr.length-1) {
				System.out.print(arr[i]+",");
			}
			else {
				System.out.println(arr[i]+"]");
			}
		}
	}

1.简单选择排序

简单选择排序是最直观的排序方法，比较符合人脑思维。
每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，每趟都能找到一个当前序列中最小（大）元素，直到所有元素排完为止

选择最小（或最大）元素主要通过不断地比较大小和交换位置来实现

public void selectSort(int[] arr) {          // i在前， j在后。  i,j比较大小，大的换到后面去
		for(int i=0; i<arr.length-1; i++) {      //  从 第一个 到 倒数第二个元素 都要和后面的每个元素进行比较
			for(int j=i+1; j<arr.length; j++) {  // j代表i后面的每一个元素
				if(arr[i]>arr[j]) {
					swap(arr,i,j);
				}
			}
		}
	}

简单选择排序通过上面优化之后，无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为n-1次。综合下来，时间复杂度为O(n^2)

2.直接插入排序

数组分为两部分：已有序、待排序
插入排序的任务：逐个把待排序的序列插入到已有序的序列的相应位置

public void insertSort(int[] arr) {
		//一开始只能保证第一个元素是已有序的序列。所以从第二个元素开始，逐个插入到已有序序列
		for(int i=1;i<arr.length;i++) {
			int j=i;
			while(j>0 && arr[j]<arr[j-1]) {   //这种情况就说明顺序开始出现问题，需要通过交换位置来调整
				swap(arr,j-1,j);  
				j--;      //一旦需要调整位置，j每次都要变化，和前面的已有序元素都要进行比较，保证当前遍历的元素在正确的位置
			}
		}
	}

简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度为O(n^2)

3.冒泡排序

对相邻的元素进行两两比较，顺序不符合要求则进行交换，
这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序
一共需要排序 arr.length-1 趟

public void bubbleSort(int[] arr) {
		for( int i=0;i<arr.length-1;i++) {       // 冒泡 趟数-----首先确定最大的元素放到了最后一个位置....一共要确定arr.length-1个元素的位置，所以一共冒泡了arr.length-1趟	
			for(int j=0; j<arr.length-1-i; j++) {   // 一趟冒泡
				if(arr[j]>arr[j+1])  {            //j和j+1比较，所以j最多只能到倒数第二个元素，即j<arr.length-1
					swap(arr,j,j+1);
				}
			}
		}
	}

若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成；若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度为O(n^2）

4.快速排序

快速排序采用“分而治之”的思想，把大的拆分为小的，小的再拆分为更小的，非常高效。

选择一个基准值（通常选择待排序的第一个元素），然后遍历整个数组，比基准值小的放在基准值左边（左子集），大的放在右边（右子集）
再通过递归，分别对左右子集重复上面的操作…直至所有子集只有一个元素，说明有序了

public void quickSort(int[] arr, int low, int high) {   //low-子集开始位置，high-子集结束位置
//1.递归出口
		if(low>high) {    //low、high从数组两端逐渐向中间靠拢，若low>high了，则代表排序已完成
			return;
		}
//2.存
		int i=low;        //把low、high存放到i,j里，接下来就通过移动i,j来实现 基准 左小，右大
		int j=high;       //不可直接操作low、high，这两个变量是下一趟才会改变的
//3.key基准
		int key=arr[low];  //假定第一个元素是基准key
//4.完成一趟排序---完成一趟后就实现了key左边都比key小，右边都比key大，但两边是无序的
		while( i<j ) {
		//4.1 从右往左找到第一个小于key的数
			while( i<j && arr[j]>key ) { j--; }   //从右往左，若元素>key，符合条件，则继续往左找，直到找到的数<key
			if(arr[j]<key) {    //如果右边有比key小的，就将i,j元素进行交换使其符合  基准左小右大
				swap(arr,j,i);
			}
			
		//4.2从左往右找到第一个大于key的数
			while( i<j && arr[i]<=key) { i++; }   //从左往右，若元素<=key，符合条件，则继续往右找，直到找到的数>key
			if(arr[i]>=key) {
				swap(arr,i,j);   
			}                          
		}                              
		                                             //arr： [ 符合，符合...符合, arr[i],...key...,arr[j],...符合，符合]
                                                     //找到左右两边各自的第一个小于/大于key（不符合条件）的元素，交换使其符合条件	
//5.递归：左边的子集进行快排
		quickSort(arr,low,i-1);   //j-1也行，下面j+1
	   //右边的子集进行快排        
		quickSort(arr,i+1,high);
 	}

最坏情况下初始序列整体或局部有序，快排性能会退化成冒泡排序，时间复杂度O(n^2)
快排的平均时间复杂度为：O(nlogn)

5.归并排序

归并排序和快速排序一样，也是采用“分而治之”的思想，区别是分组策略不同：
快排根据和基准值比较大小来分为两组；
归并排序则是把待排序元素放在数组里，数组前一半为一组，后一半为另一组。

归并排序是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))

算法步骤：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针达到序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

 //两路归并算法，两个排好序的子序列合并为一个子序列
    public void merge(int []a,int left,int mid,int right){
        int []tmp=new int[a.length];//步骤1：定义辅助数组
        int p1=left,p2=mid+1,k=left;//步骤2：p1、p2是检测指针，k是存放指针

        while(p1<=mid && p2<=right){  //步骤3：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
            if(a[p1]<=a[p2])
                tmp[k++]=a[p1++];
            else
                tmp[k++]=a[p2++];
        }

        while(p1<=mid) tmp[k++]=a[p1++];//步骤5：如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while(p2<=right) tmp[k++]=a[p2++];//同上

        //复制回原数组
        for (int i = left; i <=right; i++) 
            a[i]=tmp[i];
    }

    public void mergeSort(int [] a,int start,int end){
        if(start<end){//当子序列中只有一个元素时结束递归
            int mid=(start+end)/2;//划分子序列
            mergeSort(a, start, mid);//对左侧子序列进行递归排序
            mergeSort(a, mid+1, end);//对右侧子序列进行递归排序
            merge(a, start, mid, end);//合并
        }
    }

6.希尔排序

希尔排序也成为“缩小增量排序”，其基本原理是，现将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序列“基本有序”后，最后在对所有元素进行一次直接插入排序
实现代码参考 https://blog.csdn.net/jianyuerensheng/article/details/51258460

7.堆排序

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
堆排序是不稳定的排序方法，辅助空间为O(1)， 最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能
实现代码参考 https://www.cnblogs.com/Java3y/p/8639937.html

以上排序算法性能对比

稳定性：序列中相等的元素，经过某排序方法后，相等元素的相对位置保持不变，该排序算法即是稳定的
举例说明：
a1,a2,a3,a4,a5 其中a2=a4, a2在a4前面
若排序后：a1,a2,a4,a3,a5 ，a2仍然在a4前面，说明算法稳定；否则不稳定

结论：

1. 稳定算法：直接插入、冒泡、归并
   不稳定：简单选择、快速、希尔、堆
2. 时间复杂度O(n^2)：直接插入、冒泡、快速、简单选择
   时间复杂度O(nlogn)：归并、堆
3. 空间复杂度O(1)：简单选择、直接插入、冒泡、希尔、堆
   空间复杂度O(n)：归并
   空间复杂度O(logn)：快速
4. 当序列整体或局部有序时，直接插入和冒泡会有较高效率；快排的效率会下降
   当排序序列较小且不要求稳定性时，直接选择排序效率较好；
   当排序序列较小且要求稳定性时，冒泡排序效率较好。