排序算法（一）

排序算法

• 排序算法稳定性
• 一、冒泡排序（Bubble Sort）
• • 排序原理
  • 时间复杂度、空间复杂度、稳定性
  • 算法代码
  • 算法优化
  • 动画排序过程（含外层循环优化）
• 二、选择排序（Selection Sort）
• • 排序原理
  • 时间复杂度、空间复杂度、稳定性
  • 算法代码
  • 算法优化
  • 动画排序过程（优化前）
• 三、插入排序（Insertion Sort）
• • 排序原理
  • 时间复杂度、空间复杂度、稳定性
  • 算法代码
  • 算法优化
  • 动画排序过程（优化前）
• 四、快速排序（Quick Sort）
• • 排序原理
  • 时间复杂度、空间复杂度、稳定性
  • 算法代码1
  • 动画排序过程
  • 算法代码2
  • 动画排序过程（单次）

排序算法稳定性

1. 排序之后，相同数组元素次序不会改变——算法稳定
2. 排序之后，相同数组元素次序可能会改变——算法不稳定

一、冒泡排序（Bubble Sort） 排序原理

1. 遍历数组，比较相邻的元素，如果前者比后者大，就交换数值，直至最后的元素是最大的数
2. 针对所有的元素重复以上的步骤，直到排序完成

时间复杂度、空间复杂度、稳定性

时间复杂度	空间复杂度	稳定性
O(n2)	O(1)	稳定

算法代码

	public void BubbleSort(int arr[]) {
        int size= arr.length;
        for (int i = 0; i < size - 1; i++){         //遍历数组
            for (int j = 0; j < size - 1 - i; j++){ //选出该趟排序的最大值往后移动
                if (arr[j] > arr[j + 1]){           //数值比较、交换
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

算法优化

• 优化内层循环
  　　在每趟循环中，记住最后一次交换发生的位置pos ，该位置之后的元素均已有序，下一趟循环 从0开始 到 pos 结束，从而减少排序的比较次数
• 优化外层循环
  　　冒泡排序过程可在某次排序后即有序。为此，引入一个标签flag，在每趟循环开始前，先将其置为false。若排序过程中发生了交换，则将其置为true。每次循环结束时检查flag，若为false，即本次循环未曾发生过交换，则终止算法不再进行下一趟排序。
• 优化代码

      public int[] BubbleSort(int arr[]) {
          int size= arr.length;
          boolean flag;    //flag：标记循环是否交换数值
          int k=size-1;
          int pos=0;		//pos：标记循环里最后一次交换的位置  
          for (int i = 0; i < size - 1; i++){         //遍历数组
              flag=false;
              for (int j = 0; j < k; j++){ //选出该趟排序的最大值往后移动
                  if (arr[j] > arr[j + 1]){           //数值比较、交换
                      int tmp = arr[j];
                      arr[j] = arr[j + 1];
                      arr[j + 1] = tmp;
                      flag=true;
                      pos=j;
                  }
              }
              k=pos;
              // 若没有交换数值，数组排序成功，结束循环
              if(!flag){
                  break;
              }
          }
          return arr;
      }
  

动画排序过程（含外层循环优化）

二、选择排序（Selection Sort） 排序原理

1. 遍历数组，在数组中找到最小元素，记录下标，存放到排序序列的起始位置
2. 再从剩余未排序元素中继续寻找最小元素，记录下标，然后放到已排序序列的末尾
3. 循环遍历，直到所有元素排序完毕

时间复杂度、空间复杂度、稳定性

时间复杂度	空间复杂度	稳定性
O(n2)	O(1)	不稳定

稳定性：序列5 8 5 2 9，第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法

算法代码

	public int[] selectionSort(int arr[]) {
        int size= arr.length;
        int minIndex = size;
        int t;
        for (int i = 0; i < size - 1; i++){         //遍历数组
            minIndex=i;
            for (int j = i+1; j < size; j++){
                if (arr[j] < arr[minIndex]){        
                    minIndex=j;                     //记录最小值下标
                }
            }
            // 将最小值交换到已排序序列的末尾
            t = arr[minIndex];
            arr[minIndex]=arr[i] ;
            arr[i]= t;
        }
        return arr;
    }

算法优化

• 在一次遍历中，同时寻找最大值与最小值的下标，分别将其放置未排序队列的最 前/后 端

	public int[] selectionSort(int arr[]) {
        int n=arr.length;
        int left = 0;
        int right = n-1;
        int t;
        while (left < right)
        {
            int min = left;
            int max = right;
            for (int i = left; i <= right ; i++)
            {
                if (arr[i] < arr[min])
                    min = i;
                if(arr[i] > arr[max])
                    max = i;
            }
          
            t=arr[max];
            arr[max]=arr[right];
            arr[right]=t;
  			//考虑修正的情况:若最小值下标=right，上一步交换将最小值赋值到max位置中——取最小值需到max位置处获取
            if (min == right)
            {
                min = max;
            }

            t=arr[min];
            arr[min]=arr[left];
            arr[left]=t;

            left++;
            right--;
        }

        return arr;
    }

动画排序过程（优化前）

三、插入排序（Insertion Sort） 排序原理

1. 从第一个元素开始，该元素可以认为已排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素向前扫描到下一位置；直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置后面

时间复杂度、空间复杂度、稳定性

时间复杂度	空间复杂度	稳定性
O(n2)	O(1)	稳定

算法代码

	public int[] InsertionSort(int arr[]){
        int n=arr.length;
        for (int i = 1; i -1 ; j--) {
                if(arr[j]>t){
                   arr[j+1]=arr[j];
                }
                else {
                    arr[j+1]=t;
                    break;
                }
            }
          -----------------------------
            //2、wile循环遍历 插入排序
            int j=i-1;
            while (j>=0 &&arr[j]>t){
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=t;
          ------------------------------
        }
        return arr;
    }

算法优化

• 向前面已排序数组插入新元素时使用二分查找法查找新元素位置

	public int[] InsertionSort2(int arr[]){
	        int n=arr.length;
	        for (int i = 1; i t){
	                    right=mid-1;
	                }else {
	                    left=mid+1;
	                }
	            }
	
	            int j=i-1;
	            while (j>=left){
	                arr[j+1]=arr[j];
	                j--;
	            }
	            arr[left]=t;
	        }
	        return arr;
	    }

动画排序过程（优化前）

四、快速排序（Quick Sort）

• 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序

排序原理

1. 从数列中挑出一个元素，称为 “基准”
2. 所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

时间复杂度、空间复杂度、稳定性

时间复杂度	空间复杂度	稳定性
O(nlog2n)	O(1)	不稳定

稳定性：序列6 100 100 1，第一遍遍历，基准数为6，第2个元素100会和第4个元素1交换,那么原序列中2个100的相对前后顺序就被破坏了,所以快速排序不是一个稳定的排序算法

算法代码1

	//循环快速排序
  public static void quickSort(int arr[],int left,int right){
        int n=arr.length-1;
        left=left<0?0:left;
        right=right>n?n:right;
        if(left 
动画排序过程 
 
算法代码2 
	public static void quickSort(int arr[],int left,int right){
        int n=arr.length-1;
        left=left<0?0:left;
        right=right>n?n:right;
        if(leftx){
                right--;
            }
            if (left 
动画排序过程（单次）