devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

十大排序算法详解（一）冒泡排序、选择排序、插入排序、快速排序、希尔排序_十大排序算法详解--华为云开发者联盟

作者：花生_TL007 | 2024-04-12 17:36:34

赞

踩

十大排序算法详解--华为云开发者联盟

文章目录

一、冒泡排序

1.1 冒泡排序基础

  冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
  冒泡排序的步骤是比较固定的：

1>比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2>每趟从第一对相邻元素开始，对每一对相邻元素作同样的工作，直到最后一对。
3>针对所有的元素重复以上的步骤，除了已排序过的元素(每趟排序后的最后一个元素)，直到没有任何一对数字需要比较。

  此处引用网上一张比较经典的gif来展示冒泡排序的整个过程：

  冒泡排序的常规实现代码如下：

	public static void bubbleSort(int[] arr) {
		/*判断数组为空或为一个元素的情况，即边界检查*/
		if (arr == null || arr.length < 2) {
			return;
		}
		
		/*规定每次两两比较的末尾元素的位置，最多为数组的最后一个位置*/
		for (int end = arr.length - 1; end > 0; end--) {
			/*从第一个元素开始，两两进行比较，如果前面的元素大于后面的
			  元素，就交换，最终的结果就是最大的数在最后面
			*/
			for (int i = 0; i < end; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

1.2 冒泡排序优化

  上个章节介绍了冒泡排序的常规实现，但是这种最简单的排序是存在着不必要的比较动作的。稍微修改上述代码，就可以查看每次比较后的结果：

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数，array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	/*内循环为每趟比较的次数，第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较，若满足条件则交换（升序为左大于右，降序反之） */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

  该代码的输出结果为：

第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9
第 4 趟，第 1 次比较后的结果：
2 3 4 5 9

  从上面的测试结果可以看出，从第2趟第3次比较后，数组元素已经处于有序状态，此后所有的比较都不必进行。

1.2.1 外循环优化

  第一种优化就基于上面的测试结果来进行，如果某次比较过程中，发现没有任何元素移动，则不再进行接下来的比较。具体的做法是在每趟比较时，引入一个boolean型变量isSwap，来判断下次比较还有没有必要进行。示例代码如下：

        int[ ] array=new int[ ]{5,2,3,9,4};
        /*外循环为排序趟数，array.length个数进行array.length-1趟 */
        for(int i=0;i<array.length-1;i++){
        	boolean isSwap=false;
        	/*内循环为每趟比较的次数，第i趟比较array.length-i次 */
            for(int j=0;j<array.length-1-i;j++){
            	 /*相邻元素比较，若满足条件则交换（升序为左大于右，降序反之） */
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    isSwap=true;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
                for(int k=0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
            /*如果没有交换过元素，则已经有序，不再进行接下来的比较*/
            if(!isSwap){
            	break;
            }
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

  测试结果如下：

第 1 趟，第 1 次比较后的结果：
2 5 3 9 4
第 1 趟，第 2 次比较后的结果：
2 3 5 9 4
第 1 趟，第 3 次比较后的结果：
2 3 5 9 4
第 1 趟，第 4 次比较后的结果：
2 3 5 4 9
第 2 趟，第 1 次比较后的结果：
2 3 5 4 9
第 2 趟，第 2 次比较后的结果：
2 3 5 4 9
第 2 趟，第 3 次比较后的结果：
2 3 4 5 9
第 3 趟，第 1 次比较后的结果：
2 3 4 5 9
第 3 趟，第 2 次比较后的结果：
2 3 4 5 9

  从上面的测试结果可以看出，已经对排序过程进行了优化，因为没有进行第4趟比较。也许有人会有疑问“第2趟比较结束后，数组已经有序了，为什么还要进行第3次比较”？之所以对此有疑问，可能是没太清楚isSwap变量的作用，该变量的作用是“假如本趟比较过程中没有交换发生，则不必进行下一趟比较”，在第2趟比较过程中，发生了交换动作，所以第3趟比较仍会进行。

1.2.2 内循环优化

  第一种优化方式比较容易理解，但同时也存在着缺点：某趟比较只要开始，哪怕数组元素已经有序，也要把该趟的所有次比较完。也就是说，第一种优化方式，只能在“趟”的级别上优化。
  第二种优化方式，也就是要实现在“次”的级别进行优化，其思路是“记下最后一次交换的位置，后边没有交换，必然是有序的，然后下一次排序从第一个比较到上次记录的位置结束即可”。示例代码为：

        int[ ] array = new int[ ]{5,2,3,7,9};
        int position = array.length - 1;
        /*外循环为排序趟数，array.length个数进行array.length-1趟 */
        for(int i = 0;i<array.length-1;i++){
        	boolean isSwap = false;
        	/*用来记录最后一次交换的位置*/
        	int newPosition = 0;
        	/*内循环为每趟比较的次数，第i趟比较array.length-i次 */
            for(int j = 0;j<position;j++){
            	 /*相邻元素比较，若满足条件则交换（升序为左大于右，降序反之） */
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    isSwap = true;
                    /*记录最后一次交换的位置*/
                    newPosition = j;
                }
                /*查看每趟比较后的数组元素*/
                System.out.println("第 "+(i+1)+" 趟，第 "+(j+1)+" 次比较后的结果：");
                for(int k = 0;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
            /*如果没有交换过元素，则已经有序，不再进行接下来的比较*/
            if(!isSwap){
            	break;
            }
            /*下趟比较所需要比较到的位置*/
            position = newPosition;
        }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

  测试结果如下：

第 1 趟，第 1 次比较后的结果：
2 5 3 7 9
第 1 趟，第 2 次比较后的结果：
2 3 5 7 9
第 1 趟，第 3 次比较后的结果：
2 3 5 7 9
第 1 趟，第 4 次比较后的结果：
2 3 5 7 9
第 2 趟，第 1 次比较后的结果：
2 3 5 7 9

  从上面的测试结果可以看出，在第2趟进行了1次比较后，数组元素已经处于有序状态，此时便不再进行接下来的比较。

1.2.3 双向遍历

  上面的两种优化都是单向遍历比较的，然而在很多时候，遍历的过程可以从两端进行，从而提升效率。因此在冒泡排序中，其实也可以进行双向循环，正向循环把最大元素移动到数组末尾，逆向循环把最小元素移动到数组首部。该种排序方式也叫双向冒泡排序，也叫鸡尾酒排序。
  关于此种排序优化，示例代码如下：

	static void bubbleSort(int[] array) {
        int arrayLength = array.length;
        
        int preIndex = 0;
        int backIndex = arrayLength - 1;
        while(preIndex < backIndex) {
            preSort(array, arrayLength, preIndex);
            preIndex++;
            
            if (preIndex >= backIndex) {
                break;
            }
            
            backSort(array, backIndex);
            backIndex--;
        }
    }
    
    // 从前向后排序
	static void preSort(int[] array, int length, int preIndex) {
        for (int i = preIndex + 1; i < length; i++) {
            if (array[preIndex] > array[i]) {
                swap(array, preIndex, i);
            }
        }
    }
    
    // 从后向前排序
	static void backSort(int[] array, int backIndex) {
        for (int i = backIndex - 1; i >= 0; i--) {
            if (array[i] > array[backIndex]) {
                swap(array, i, backIndex);
            }
        }
    }
	
	static void swap (int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

1.3 冒泡排序的稳定性、复杂度和适用场景

  空间复杂度 O(1)。

1.3.1 稳定性

  在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。

1.3.2 时间复杂度

  如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序)，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：
        
  冒泡排序最好的时间复杂度为O(n)。

  如果待排序序列是反序(如我们希望的结果是升序，待排序序列是降序)的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
        在这里插入图片描述
  冒泡排序的最坏时间复杂度为O(n2)。
  综上，因此冒泡排序总的平均时间复杂度为O(n2)。

1.3.3 适用场景

  冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。

二、选择排序

2.1 选择排序基础

  选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置直到未排序元素个数为0。
  选择排序的步骤：

1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2>再从剩余未排序元素中继续寻找最小（大）元素，然后放到未排序序列的起始位置。
3>重复第二步，直到所有元素均排序完毕。

  此处引用网上一张比较经典的gif来展示选择排序的整个过程：

  用代码来实现上述过程，示例如下：

	public static void selectionSort(int[] arr) {
		/*判断数组为空或为一个元素的情况，即边界检查*/
		if (arr == null || arr.length < 2) {
			return;
		}

		/*每次要进行比较的两个数，的前面那个数的下标*/
		for (int i = 0; i < arr.length - 1; i++) { 
			//min变量保存该趟比较过程中，最小元素所对应的索引，
			//先假设前面的元素为最小元素
			int minIndex = i;
			/*每趟比较，将前面的元素与其后的元素逐个比较*/
			for (int j = i + 1; j < arr.length; j++) {
				//如果后面的元素小，将后面元素的索引极为最小值的索引
				if(arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			//然后交换此次查找到的最小值和原始的最小值
			swap(arr, i, minIndex);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

2.2 选择排序优化

2.2.1 选择排序优化图示

  选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。第一次选择最大值与最小值，过程如下：
      

2.2.2 选择排序优化实现

  示例代码如下：

        /*初始化左端、右端元素索引*/
	    int left = 0;
	    int right = len - 1;
	    while (left < right){
	    	/*初始化最小值、最大值元素的索引*/
	        int min = left;
	        int max = right;
	        for (int i = left; i <= right; i++){
	        	/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
	            if (arr[i] < arr[min])
	                min = i;
	            if (arr[i] > arr[max])
	                max = i;
	        }
	        /*最大值放在最右端*/
	        int temp = arr[max];
	        arr[max] = arr[right];
	        arr[right] = temp;
	        /*此处是先排最大值的位置，所以得考虑最小值（arr[min]）在最大位置（right）的情况*/
	        if (min == right)
	            min = max;
	        /*最小值放在最左端*/
	        temp = arr[min];
	        arr[min] = arr[left];
	        arr[left] = temp;
	        /*每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1*/
	        left++;
	        right--;
	    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

2.3 选择排序的稳定性、复杂度及适用场景

  空间复杂度 O(1)。

2.3.1 稳定性

  在选择排序中，每趟都会选出最大元素与最小元素，然后与两端元素交换，此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[5,3,5,2,9]，在array[0]与array[3]元素交换时，序列的稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。

2.3.2 时间复杂度

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

2.3.3 适用场景

  待排序序列中，元素个数较少时。

三、插入排序

3.1 插入排序基础

  插入排序也是一种常见的排序算法，插入排序的思想是：将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
  插入排序的步骤如下：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。

  假如有[5,2,3,9,4,7]六个元素，下面就以排序过程中的一个步骤（此时有序部分为[2,3,5,9]，无序部分为[4,7]，接下来要把无序部分的“4”元素插入到有序部分），来展示一下插入排序的运行过程。

  1. 首先，原始的数组元素是这样的。
          
      其中，浅绿色代表有序部分，黄色代表无序部分。
  2. 在无序部分中挑出要插入到有序部分中的元素。
          
  3. 将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 9，所以9向后移，4向前移。
          
  4. 继续将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 5，所以5向后移，4继续向前移。
          
  5. 继续将4与3比较。由于4>3，所以不再向前比较，插入到当前位置。
          
  6. 此时有序部分，由[2,3,5,9]变成[2,3,4,5,9]。
          

  将上述过程用代码实现，示例如下：

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		
		//每次将从0-i位置的元素进行排序
		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
			//int j = i - 1; j >= 0表示左边位置的边界条件
			//arr[j] > arr[j + 1]表示最右边的数与相邻数的比较
			//j--表示将这个过程向左推进
			//swap(arr, j, j + 1)表示进行两个相邻数比较时，左边的数大于右边数时，才交换否则不交换
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

3.2 插入排序优化

  插入排序的常见优化方式：折半插入排序。
  该类优化有二分的思想，是在将待排序的元素与有序部分的元素比较时，不再挨个比较，而是用二分折中的方式进行比较，加快比较效率。示例代码如下：

	    int j,low,mid,high,temp;
	    for(int i = 1;i<n;i++){
	        low = 0;
	        high = i-1;
	        temp = arr[i];
	        /*找到合适的插入位置high+1，如果中间位置元素
	         *比要插入元素大，则查找区域向低半区移动，否
	         *则向高半区移动
	         */
	        while(low <= high){
	            mid = (low+high)/2;
	            if(arr[mid]>temp){
	                high = mid-1;
	            }else{
	                low = mid+1;
	            }
	        }
	        /*high+1后的元素后移*/
	        for(j = i-1;j >= high+1;j--)    
	        {
	            arr[j+1] = arr[j];
	        }
	        /*将元素插入到指定位置*/
	        arr[j+1] = temp;    
	    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

3.3 插入排序的稳定性、复杂度和适用场景

  空间复杂度 O(1)。

3.3.1 稳定性

  在使用插入排序时，元素从无序部分移动到有序部分时，必须是不相等(大于或小于)时才会移动，相等时不处理，所以直接插入排序是稳定的。

3.3.2 时间复杂度

  在插入排序中，当待排序序列是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较n- 1次，时间复杂度为O(n)。
  最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(n2)。
  平均来说，array[1…j-1]中的一半元素小于array[j]，一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是O(n2)。

3.3.3 适用场景

  待排序序列的元素个数不多(<=50)，且元素基本有序。

四、快速排序

4.1 快速排序基础

  快速排序也是一种较为基础的排序算法，其效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一趟只能选出一个最值，有n个元素最多就要执行n - 1趟比较。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
  快速排序的思想是：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
  快速排序的步骤如下：

1>先从数列中取出一个数作为基准数。
2>分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3>再对左右区间重复第二步，直到各区间只有一个数。

  快排的不同版本，演进过程示例：

	public static void quickSort1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process1(arr, 0, arr.length - 1);
	}

	//第一版快排，这一版的时间复杂度为O(n2)
	public static void process1(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		//在[L,R]范围上，根据arr[R]，模仿netherlandsFlag方法，
		//将数组分为三个部分：<=arr[R]的部分，arr[R]本身，>=
		//arr[R]的部分，这样确定了在最终的数组中arr[R]的位置，
		//并返回这个位置
		int M = partition(arr, L, R);
		//接下来只要在左右两侧重复这个过程就行
		process1(arr, L, M - 1);
		process1(arr, M + 1, R);
	}

	public static int partition(int[] arr, int L, int R) {
		if (L > R) {
			return -1;
		}
		if (L == R) {
			return L;
		}
		int lessEqual = L - 1;
		int index = L;
		while (index < R) {
			if (arr[index] <= arr[R]) {
				swap(arr, index, ++lessEqual);
			}
			index++;
		}
		swap(arr, ++lessEqual, R);
		return lessEqual;
	}

	
	public static void quickSort2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process2(arr, 0, arr.length - 1);
	}

	//第二版快排：相比第一版的区别/优势：在于一次可以确定
	//相等基准值的一个区域，而不再只是一个值
	//第二版的时间复杂度为O(n2)
	public static void process2(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		int[] equalArea = netherlandsFlag(arr, L, R);
		process2(arr, L, equalArea[0] - 1);
		process2(arr, equalArea[1] + 1, R);
	}
	
	//这个方法的目的是按arr[R]为基准值，将arr数组划分为小于基准值、
	//等于基准值、大于基准值三个区域
	
	//在arr[L...R]上，以arr[R]做基准值，在[L...R]范围内，<arr[R]的数
	//都放在左侧，=arr[R]的数放在中间，>arr[R]的数放在右边
	//返回的值为和arr[R]相等的范围的数组
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
		if (L > R) {
			return new int[] { -1, -1 };
		}
		if (L == R) {
			return new int[] { L, R };
		}
		//小于基准值的区域的右边界
		int less = L - 1;
		//大于基准值的区域的左边界
		int more = R;
		int index = L;
		while (index < more) {
			//等于基准值，不做处理，判断下一个数据
			if (arr[index] == arr[R]) {
				index++;
			//当前数小于基准值
			} else if (arr[index] < arr[R]) {
				//将当前值和小于区域右边的一个值交换：swap
				//判断下一个数据：index++
				//小于区域右移：++less（先++是为了完成swap）
				swap(arr, index++, ++less);
			} else {
				//将当前值和大于区域左边的一个值交换：swap
				//大于区域左移：--more（先--是为了完成swap）
				swap(arr, index, --more);
			}
		}
		//因为最开始是把arr[R]作为基准值的，所以在进行接下来的一步之前，
		//arr[R]实际是在大于区域的最右侧的，所以还需要进行一步交换，这样
		//整个数组就成了小于区域、等于区域、大于区域的样子
		swap(arr, more, R);
		//less + 1是等于区域的起始位置，more经过上一步的和arr[R]交换后，
		//就成了等于区域的结束位置
		return new int[] { less + 1, more };
	}
	

	public static void quickSort3(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process3(arr, 0, arr.length - 1);
	}

	//第三版快排：不再固定去arr[R]，改为去随机位置的值，然后
	//和arr[R]进行交换，接下来的过程就和第二版一样
	
	//第三版的复杂度变化了，是O(nlogn)，该事件复杂度是最终求
	//的是数学上的一个平均期望值
	public static void process3(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
		int[] equalArea = netherlandsFlag(arr, L, R);
		process3(arr, L, equalArea[0] - 1);
		process3(arr, equalArea[1] + 1, R);
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132

  在选择基准值的时候，越靠近中间，性能越好；越靠近两边，性能越差。第三版随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件。把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N。那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望。
  时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。

4.2 快速排序优化

4.2.1 三数取中

  该方法指的是选取基准值时，不再取固定位置(如第一个元素、最后一个元素)的值，因为这种固定取值的方式在面对随机输入的数组时，效率是非常高的。但是一旦输入数据是有序的，使用固定位置取值，效率就会非常低。因此此时引入了三数取中，即在数组中随机选出三个元素，然后取三者的中间值做为基准值。

4.2.2 插入排序

  当待排序序列的长度分割到一定大小(如 < 10)后，使用插入排序。

4.2.3 相等元素聚集（上个小节中的第二版快排）

  在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割。

4.3 快速排序的稳定性、复杂度和适用场景

4.3.1 稳定性

  在使用快速排序时，每次元素分堆都要选择基准因子。此时，基准因子两边都有可能出现和基准因子相同的元素，如序列[1,3,2,4,3,4,6,3]，如果选择了array[4]作为基准因子，那么array[1]和array[7]势必会被分到基准因子的同一侧，序列的稳定性被破坏。所以，快速排序是一种不稳定的排序算法。

4.3.2 复杂度

  快速排序的空间复杂度 O(logn)。
  快速排序的时间复杂度是O(nlogn)【上小节第三版的时间复杂度】。

  对于规模为 n 的问题，一共要进行 log(n) 次的切分，和基准值进行 n-1 次比较，n-1 次比较的时间复杂度是 O(n)，所以快速排序的时间复杂度为 O(nlogn)。
  但是，如果每次在选择基准值的时候，都不幸地选择了子数组里的最大或最小值。即每次把数组分成了两个更小长度的数组，其中一个长度为 1，另一个的长度是子数组的长度减 1。这样的算法复杂度变成 O(n²)。
  和归并排序不同，快速排序在每次递归的过程中，只需要开辟 O(1) 的存储空间来完成操作来实现对数组的修改；而递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数。

4.3.3 适用场景

  快速排序的适用场景是：待排序序列元素较多，并且元素较无序。

五、希尔排序

5.1 希尔排序基础

  希尔排序又称为缩小增量排序，是对之前介绍的插入排序的一种优化版本，优化的地方在于：不用每次插入一个元素时，就和序列中有序部分中的所有元素进行比较。
  该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于序列元素总数）作为间隔，所有距离为increment的元素放在同一个逻辑数组中，在每一个逻辑数组中分别实行直接插入排序。然后缩小间隔increment，重复上述逻辑数组划分和排序工作。直到最后取increment=1，将所有元素放在同一个数组中排序为止。
  其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤：
   1>选increment，划分逻辑分组，组内进行直接插入排序。
   2>不断缩小increment，继续组内进行插入排序。
   3>直到increment=1，在包含所有元素的序列内进行直接插入排序。

5.1.1 排序过程图示

  1>假如有[5,2,3,9,4,7]六个元素，第一趟取increment的方法是：6/3向下取整+1=3。将整个数据列划分为间隔为3的3个逻辑分组，然后对每一个逻辑分组执行直接插入排序，相当于对整个数组执行了部分排序调整。

  2>第二趟将间隔increment= increment/3向下取整+1=2，将整个数组划分为2个间隔为2的逻辑分组，分别进行排序。

  3>第3趟继续缩小间隔。间隔缩小为increment= increment/3向下取整+1=1，当增量为1的时候，实际上就是把整个数列作为一个逻辑分组进行插入排序。

5.1.2 排序过程实现

  上述图示对应的代码实现，示例如下：

		/*初始化划分增量*/
		int increment = len;	
		int temp;
		/*每次减小增量，直到increment = 1*/
		while (increment > 1){	
			/*增量的取法之一：除三向下取整+1*/
			increment = increment/3 + 1;
			/*对每个按增量划分后的逻辑分组，进行直接插入排序*/
			for (int i = increment; i < len; ++i) {	
				if (arr[i-increment] > arr[i]) {
					temp = arr[i];
					int j = i-increment;
					/*移动元素并寻找位置*/
					while (j >= 0 && arr[j] > temp) {	
						arr[j+increment] = arr[j];
						j -= increment;
					} 
					/*插入元素*/
					arr[j+increment] = temp;	
				}
			}
		} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

  从上述代码可以看出，希尔排序的代码与直接插入排序的代码十分相似。因为希尔排序本就是直接插入排序的优化版本，不同的地方就是间隔慢慢减成1，直接插入排序的间隔一直就是1。

5.2 希尔排序优化

  由于希尔排序是基于插入排序的，所以在插入排序中也可运用直接插入排序中的优化方式，此处以二分折中的方式来优化希尔排序，示例代码如下：

	   /*初始化划分增量*/
	   int increment = len;	
	   int j,temp,low,mid,high;
	   /*每次减小增量，直到increment = 1*/
	   while (increment > 1){	
		  /*增量的取法之一：除三向下取整+1*/
		  increment = increment/3 + 1;
		  /*对每个按增量划分后的逻辑分组，进行直接插入排序*/
		  for (int i = increment; i < len; ++i) {	
			 low = 0;
			 high = i-1;
			 temp = arr[i];
	         while(low <= high){
	            mid = (low+high)/2;
	            if(arr[mid]>temp){
	                high = mid-1;
	            }else{
	                low = mid+1;
	            }
	         }
	         j = i-increment;
		     /*移动元素并寻找位置*/
			 while(j >= high+1){	
				arr[j+increment] = arr[j];
				j -= increment;
			 } 
			 /*插入元素*/
			 arr[j+increment] = temp;	
		  }
	   }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

5.3 希尔排序的稳定性、复杂度及适用场景

5.3.1 稳定性

  希尔排序是直接插入排序的优化版，在排序过程中，会根据间隔将一个序列划分为不同的逻辑分组，在不同的逻辑分组中，有可能将相同元素的相对位置改变。如[2,2,4,1]，按间隔为2，降序排序，前两个元素的相对位置就会改变。因此，希尔排序是不稳定的排序方式。

5.3.2 时间复杂度

  希尔排序在最坏情况下的时间复杂度为O(n2)，平均情况下的时间复杂度为O(n1.3)。

5.3.3 适用场景

  待排序序列元素较少时。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/411869
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号