内部排序

骑猪看日落 2022-03-16 05:06 130阅读 0赞

稳定：不改变同等大小的顺序，7,6(1),6(2),5 ，不会变成6(2),6(1), 稳定排序（需谨慎关注=）  
内部排序：内存中完成  
外部排序：数据量大，需外存访问，可内存中放一部分，先对一部分排序，后面再调取数据排序  
最好：12345 最差：54321 有些时候需计算最好最差情况的时间复杂度  
1 冒泡排序：多次比较，一次比较一半概率交换，先把最大的放右边

public void bubbleSort(int []a){
               int len=a.length;
               for(int i=0;i<len;i++){  // i<len-1也可以，len-1里层循环无法运行
                   for(int j=0;j<len-i-1;j++){//注意第二重循环的条件
                       if(a[j]>a[j+1]){  // 相等不交换，保证稳定性
                           int temp=a[j];
                           a[j]=a[j+1];
                           a[j+1]=temp;
                       }
                   }
               }
           }

比较: n(n-1)/2 交换：n(n-1)/4, 稳定

2 简单选择排序（选择排序类别下）：找出最小的，与第一个交换，也可以找最大的与最后一个交换

public void selectSort(int[]a){
            int len=a.length;
            for(int i=0;i<len;i++){   //循环次数, i<len-1也可以
                int position=i;
                for(int j=i+1;j<len;j++){  //找到最小位置
                    if(a[j]<a[position]){
                        position=j;
                    }
                }
                int temp=a[position];
                a[position]=a[i];//进行交换
                a[i]=temp;
            }
        }

比较: n(n-1)/2 交换：n-1 , 不稳定（5 8 5 2 9，第一个5和2交换，排在第二个5后面了）

3 直接插入排序（插入排序类别下）：设想已存在有序序列，一个一个插入

public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int j = i;  // j初始为i，减减到1，当然碰到arr[j - 1]不大于arr[j]也退出
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr,j,j-1);
                j--;
            }
        }
    }

比较: n(n-1)/4 （平均估值） 交换：n(n-1)/4 （平均估值，应该少于比较次数，arr\[j\] >= arr\[j - 1\]最后一次比较不交换），稳定

4 希尔排序（插入排序类别下）  
考虑到直接插入排序在比较有序的情况下效率很高，所以先按某增量序列进行直接插入排序，然后不断减少增量，最后全体元素进行直接插入排序

public static void sort(int[] a) {
    for (int d = a.length / 2; d >= 1; d = d / 2) { // 初定为数组长度的一半，按一半减小，如5变成2，最小到1
        for (int i = 0; i < d; i++) {
    	   for (int j = d + i; j < a.length; j = j + d) { // 开始直接插入排序
    	     int k = j;
    	     while (k >= d && a[k] < a[k - d]) {
    		   int temp = a[k];
    		   a[k] = a[k - d];
    		   a[k - d] = temp;
    		   k = k - d;
    	    }
    	 }
        }
     }
    }

时间复杂度依赖序列选取， 一般在 O(N^1.3) 到 O(N^2) ，不稳定（1977，按步长2来后面的7就去前面了）

5 快速排序：找基准（一般首位），左边小于(等于)基准，右边大于(等于)基准，然后分别对左右排序  
若选择首位作为基准，那么右哨兵先出动，两哨兵碰头（右先出动，碰头位置是小于基准的数）的位置和基准交换

void quicksort(int[] a, int left, int right) {
    	if(left > right){ // left>=right 也可以，一个数其实也没必要排序
    		return;
    	}
        int  temp = a[left]; //temp中存的就是基准数
        int i = left;
        int j = right;
        while(i != j) { //顺序很重要，要先从右边开始找
        	while(a[j] >= temp && i < j){  // a[j]=temp,不用交换，留在原位置，当然算法本身不稳定，交换了也问题不大
        		j--;
        	}
        	while(a[i] <= temp && i < j){
        		i++;       
        	}
        	if(i < j) //交换i,j   i=j 已经碰头，没必要交换，马上就出去
        	{
        		int t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(a, left, i-1);//继续处理左边的，这里是一个递归的过程
        quicksort(a, i+1, right);//继续处理右边的 ，这里是一个递归的过程
    }

平均O(NlogN) （8个数，拆分2份，比较8次，拆分4份，比较8次，拆分8份，比较8次），最差O(n^2)，最差（总是N个数分为1和N-1），不稳定（5774239，两个7换到右边交换了顺序）

6 归并排序：考虑对已经排好序的两个序列进行合并

public static void sort(int[] a, int left, int right) {
    	if (left >= right) { // =一个数没必要排序，>一般不会出现，可能会传错
    	    return;
    	}
    	int middle = (left + right) / 2;
    	sort(a, left, middle);
    	sort(a, middle + 1, right);
    	int tmp[] = new int[right - left + 1];
    	int i = left;
    	int j = middle + 1;
    	int k = 0;
    	while (i <= middle && j <= right) {
    	    if (a[i] <= a[j]) {
    		tmp[k++] = a[i++];
    	    } else {
    		tmp[k++] = a[j++];
    	    }
    	}
    	while (i <= middle) {
    	    tmp[k++] = a[i++];
    	}
    	while (j <= right) {
    	    tmp[k++] = a[j++];
    	}
    	int n = 0;
    	for (int m = left; m <= right; m++) {
    	    a[m] = tmp[n++];
    	}
        }

时间复杂度各种情况下都为O(NlogN) ，但是需要O(N)空间，稳定

7堆排序：  
堆：完全二叉树，对任一节点，其子节点小于等于它（大顶堆），或者大于等于它（小顶堆）

public static void sort(int[] a) {
    for (int i = (a.length - 1) / 2; i >= 0; i--) { // 无论最后的叶子节点是左节点还是右节点，其父节点都为(a.length - 1) / 2
        heapAdjust(a, i, a.length);
    }
    for (int i = a.length - 1; i >= 1; i--) { // i=0 没必要自己和自己交换
        int tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        heapAdjust(a, 0, i); // 堆随着i不断减小
    }
    }
    
    public static void heapAdjust(int[] a, int i, int length) { // 数组a，长度length所构成的堆结构里，从i开始向下调整
    while (true) { // 不断向下调整
        int tmp = 0;
        if (2 * i + 1 >= length) { // 无左子节点，退出
    	break;
        }
        if (2 * i + 2 >= length) { // 无右子节点，只有左子节点，可能需交换后退出
    	if (a[i] < a[2 * i + 1]) {
    	    tmp = a[i];
    	    a[i] = a[2 * i + 1];
    	    a[2 * i + 1] = tmp;
    	}
    	break;
        }
        if (a[i] >= a[2 * i + 1] && a[i] >= a[2 * i + 2]) { // i最大，无需交换，退出
    	break;
        } else if (a[2 * i + 1] >= a[2 * i + 2]) { // 左子节点最大，和左子交换，左子继续调整
    	tmp = a[i];
    	a[i] = a[2 * i + 1];
    	a[2 * i + 1] = tmp;
    	i = 2 * i + 1;
        } else { // 右子节点最大，和右子交换，右子继续调整
    	tmp = a[i];
    	a[i] = a[2 * i + 2];
    	a[2 * i + 2] = tmp;
    	i = 2 * i + 2;
        }
    }
    }

时间复杂度各种情况下都为O(NlogN) ，不稳定

8基数(桶)排序： 先个位排，然后放回原数组，然后十位排

public static void sort(int[] a, int d) { //最大位数传入
    int[][] tmp = new int[10][a.length]; //10个桶
    int[] order = new int[10];  //记录每个桶有多少个数，初始为0
    int m = 1;
    int n = 1;
    int k = 0;
    while (m <= d) {
        for (int i = 0; i < a.length; i++) { // 入桶
    	int j = (a[i] / n) % 10; // 937取3,先除10得到93，93取个位按10取商
    	tmp[j][order[j]] = a[i]; 
    	order[j]++;
        }
        for (int i = 0; i < 10; i++) { //已入桶数据(一定程度有序)放回原数组
    	if (order[i] != 0) { 
    	    for (int j = 0; j < order[i]; j++) {
    		a[k++] = tmp[i][j];
    	    }
    	    order[i] = 0; //放完记得桶内计数清0
    	}
        }
        k = 0;
        n *= 10;
        m++;
    }
    }

时间复杂度各种情况下**大致**为O(N∗M) ，即数据个数乘数据位数， 空间复杂度为O(N)，其实为10N， 稳定

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvYmV4emY_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tvYmV4emY_size_16_color_FFFFFF_t_70]: /images/20220316/726878b592824fd896cc4c28c3a9674f.png