排序算法Java实现

红太狼 2022-05-19 01:48 154阅读 0赞

## 不稳定排序 ##

> 选择排序：  
> 经过第一轮比较得到的最小的记录，与第一个记录的位置交换， 然后对不包括第一个记录以外的记录进行第二轮比较，得到的最小记录与第二个记录交换  
> 时间复杂度：O(n^2)  
> 空间复杂度：O(1)

public static void selectSort(int[] arr){
            if (arr == null || arr.length == 0)
                return;
            int len = arr.length;
            for (int i = 0; i < len; i++) {
                int min = arr[i];
                int index = i;
                for (int j = i+1; j < len; j++) {
                    if (arr[j] < min) {
                        min = arr[j];
                        index = j;
                    }
                }
                arr[index] = arr[i];
                arr[i] = min;
            }
        }

> 快速排序：  
> 对于一组给定的记录，每一趟排序后，将原来序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分记录进行快速排序  
> 时间复杂度：O(nlogn) 最坏：O(n^2)  
> 空间复杂度：O(nlogn)

public int Partition(int[] a,int start,int end){ int std = a[start];
            while (start < end){ while(start < end && a[end] >= std) end--;
                 a[start] = a[end];
                 while(start < end && a[start] <= std) start++;
                 a[end] = a[start];
            }
            a[start] = std;
            return start;
        }
        public void quickSort(int[] a,int start,int end){ if(start >= end){ return;
            }
            int index = Partition(a,start,end);
            quickSort(a,start,index-1);
            quickSort(a,index+1,end);
        }

> 堆排序：完全二叉树  
> 将二叉树调整为大顶堆，然后将堆的最后一个元素与堆顶元素（即二叉树的根结点）进行交换后，堆的最后一个元素即为最大记录；接着将前n-1个元素调整为大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录重复该过程直到调整的堆中只剩一个元素为止，该元素即为最小记录，此时可得到一个有序序列  
> 时间复杂度：O(nlogn)  
> 空间复杂度：O(1)

public void HeapSort(int[] a){
            for (int i = a.length/2 - 1; i >= 0 ; i--) {
                HeapAdjust(a,i,a.length-1);
            }
            for (int i = a.length - 1; i >= 0; i--) {
                swap(a,0,i);
                HeapAdjust(a,0,i-1);
            }
        }
        private void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public void HeapAdjust(int[] arr,int s,int len){
            int tmp = arr[s];
            for (int i = s * 2 + 1; i < len ; i = i * 2 + 1) {
                if (i < len && arr[i] < arr[i+1]){
                    i++;
                }
                if (tmp > arr[i])
                    break;
                arr[s] = arr[i];
                s = i; //s记录被替换的子结点的索引
            }
            arr[s] = tmp;
        }

## 稳定排序 ##

> 直接插入排序：  
> 第一个记录可以看作是自成一个有序序列，其余记录称为无序序列。 接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入之前的有序序列中，直到最后一个记录插入到有序序列中为止  
> 时间复杂度：O(n^2)  
> 空间复杂度：O(1)

public static void insertSort(int[] arr){
            if (arr == null || arr.length == 0)
                return;
            int len = arr.length;
            for (int i = 1; i < len; i++) {
                int curr = arr[i];
                int j = i;
                if (arr[j-1] > curr){
                    while (j > 0 && arr[j-1]> curr){
                        arr[j] = arr[j-1];
                        j--;
                    }
                }
                arr[j] = curr;
            }
        }

> 冒泡排序：  
> 从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中最大的记录将位于第n位，然后对前面的n-1个记录进行第二轮比较，重复该过程直到进行比较的记录只剩下一个为止  
> 时间复杂度：O(n^2)  
> 空间复杂度：O(1)

public void bubbleSort(int[] arr){
            boolean flag = true;
            for (int i = 0; i < arr.length && flag; i++) {
                flag = false;
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j+1]){
                        flag = true;
                        swap(arr,j,j+1);
                    }
                }
            }
        }
        private void swap(int[] arr, int j, int i) {
            int tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = tmp;
        }

> 归并排序：归：递归，并：分开的数据有序合并  
> 将每两个相邻的长度为1的子序列进行归并，得到n/2个长度为2或1的有序子数列，再将两两归并，反复执行此过程，直到得到一个有序序列  
> 时间复杂度：O(nlogn)  
> 空间复杂度：O(n)

public static void mergeSort(int[] arr,int begin,int end){
            int mid = (begin+end)/2;
            if (begin < end){
                mergeSort(arr,begin,mid);
                mergeSort(arr,mid+1,end);
                Merge(arr,begin,end,mid);
            }
        }
        public static void Merge(int[] arr,int begin,int end,int mid){
            int[] temp = new int[end-begin+1];
            int i = begin;
            int j = mid+1;
            int k=0;
            while (i <= mid && j <= end){
                if (arr[i] < arr[j]){
                    temp[k++] = arr[i++];
                }else{
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid){
                temp[k++] = arr[i++];
            }
            while (j <= end){
                temp[k++] = arr[j++];
            }
            for (int m = 0;m < temp.length;m++){
                arr[m+begin] = temp[m];
            }
        }