java实现排序算法，比较时间复杂度

分手后的思念是犯贱 2021-09-29 15:56 336阅读 0赞

> 插入排序、冒泡排序、选择排序、快速排序、归并排序

*以下所有排序都是实现升序*

### 1.插入排序 ###

**【定义】**

*  第一个元素自成一个有序数组A，从第二个元素开始，把每一个元素插入到有序数组A中合适的位置，满足有序的条件。直到最后元素，至此构建成一个有序数组。

**【时间复杂度】**

*  O(n2)

**【代码】**

public void method(int [] array) { 
            int length = array.length;
    
            int i,j;
    
            for (i = 1; i < length; i++) { 
                int temp = array[i];
                for (j = i-1; j >= 0 && array[j] > temp; j --) { 
    
                    array[j+1] = array[j];
                }
                array[j+1] = temp;
            }
        }
    补充：
    在第二个for循环中，判断条件需要加上比较大小关系，
    不能在for循环里面进行if判断，因为这样会导致最后一个元素的判断存在问题

--------------------

### 2.冒泡排序 ###

**【定义】**

*  从第一个元素开始，进行两两比较，如果前一个大于后一个，则进行交换，经过一轮交换之后，也就是一次冒泡，最大的元素就会在最后一个位置，在从第一个元素进行排序，两两比较，经过一轮交换之后，第二大的元素就在倒数第二个位置，以此类推

**【时间复杂度】**

*  O(n2)

**【代码】**

public void method(int [] a) { 
            int i,j;
            for (i = a.length; i > 0; i --) { 
                for (j = 0; j < i-1; j ++) { 
                    if (a[j] > a[j+1]) { 
                        int temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
                    }
                }
            }
        }
    
    改进：
    可以通过加标志位，当一次冒泡没有发生交换的时候，
    也就意味着此时是排好序的
    
    public void BetterMethod(int [] a) { 
            int i,j;
            boolean flag = false;
            for (i = a.length; i > 0; i --) { 
                flag = false;
                for (j = 0; j < i-1; j ++) { 
                    if (a[j] > a[j+1]) { 
                        flag = true;
                        int temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
                    }
                }
                if (!flag) { 
                    break;
                }
            }
        }

--------------------

### 3.选择排序 ###

**【定义】**

*  在第一个元素到最后一个元素之间寻找一个最小的元素放在第一位，在从第二个元素到最后一个元素选择一个最小的放在第二位，依次类推

**【时间复杂度】**

*  O(n2)

**【代码】**

public void method(int [] a) { 
            int i,j;
            for (i = 0; i < a.length-1; i++) { 
                int index = i;
                for (j = i+1; j < a.length; j++) { 
                    if (a[j] < a[index]) { 
                        index = j;
                    }
                }
                if (i != index) { 
                    int temp = a[i];
                    a[i] = a[index];
                    a[index] = temp;
                }
            }
        }

--------------------

### 4.快速排序 ###

**【定义】**

*  快速排序需要通过递归的方法来实现，首先需要选择一个支点，这个支点理论是可以任意选择，但通常都选择中间的元素，然后从在头和尾放置索引开始同时向中间遍历，当头索引遇到大于支点的元素停止，当尾索引遇到小于支点的元素停止，然后交换头尾索引的元素，之后头尾索引交叉停止，递归的遍历，直到首尾相等

**【时间复杂度】**

*  O(nlogn)

**【代码】**

public class QuickSort { 
        public static void quickSort(int[] arr,int low,int high){ 
            int i,j,temp,t;
            if(low>high){ 
                return;
            }
            i=low;
            j=high;
            //temp就是基准位
            temp = arr[low];
     
            while (i<j) { 
                //先看右边，依次往左递减
                while (temp<=arr[j]&&i<j) { 
                    j--;
                }
                //再看左边，依次往右递增
                while (temp>=arr[i]&&i<j) { 
                    i++;
                }
                //如果满足条件则交换
                if (i<j) { 
                    t = arr[j];
                    arr[j] = arr[i];
                    arr[i] = t;
                }
     
            }
            //最后将基准为与i和j相等位置的数字交换
             arr[low] = arr[i];
             arr[i] = temp;
            //递归调用左半数组
            quickSort(arr, low, j-1);
            //递归调用右半数组
            quickSort(arr, j+1, high);
        }

**【注意】**

*  选准基准点之后，首尾设置索引，需要先从右向左遍历，在从左向右遍历，这里顺序不能颠倒，颠倒顺序算法就错误，因为一次快排要达到左边元素都小于基准点，右边元素都大于基准点，如果先从左边开始，会在大于基准点的位置停止，这个时候在交换，会在这个大于的元素跟基准点交换。
 *  在内层的索引while循环的条件：temp<=arr\[j\]&&i<j，中的等于号不能省略，因为首索引从基准点开始，索引要保证完全大于或小于才跳出循环。
 *  在外层的while循环结束之后，i和j一定是相等的，此时递归的条件，写i和j都可以。

### 5.归并排序 ###

**【定义】**

*  二路归并排序需要通过递归实现，运用的是分而治之的思想，先分再合，先是不断的分元素，直到每组元素只能一个，然后是合并，合并的时候，以中间为区分，分别在两组的首元素上设置索引，构建一个临时数组，比较索引所在的元素并把较小的放入临时数组，直到其中一组元素为空，这个时候再把另一组的元素全部放入临时数组。最后把临时数组元素拷贝到目标数组

**【时间复杂度】**

*  O(nlogn)

**【代码】**

/** * 排序 * */
        public void sort(int [] a,int s, int e) { 
            // 当只剩一个元素返回
            if (s < e) { 
                // 获取中间下标
                int mid = (s + e)/2;
                sort(a, s, mid);
                sort(a, mid+1, e);
                // 合并两个组的元素
                merge(a, s, mid, e);
            }
        }
    
        /** * 合并元素 * */
        public void merge(int [] a,int s, int mid, int e) { 
            // 临时数组
            int [] temp = new int[e-s+1];
    
            int i = s;
            int j = mid + 1;
            int index = 0;
    
            // 把两组元素比较，并以此放入临时数组，直到其中一组元素为空
            while (i<=mid && j<=e) { 
                if (a[i] < a[j]) { 
                    temp[index ++] = a[i ++];
                } else { 
                    temp[index ++] = a[j ++];
                }
            }
    
            // 把剩下的不为空的一组元素放入临时数组
            while (i <= mid) { 
                temp[index ++] = a[i ++];
            }
    
            while (j <= e) { 
                temp[index ++] = a[j ++];
            }
    
            // 把临时数组复制到目标数组
            index = 0;
            while (s <= e) { 
                a[s ++] = temp[index ++];
            }
        }

### 稳定性 ###

*  插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
 *  选择排序、希尔排序（插入排序的一种改进）、快速排序、堆排序是不稳定的。

### 关于快排和归并排序 ###

快排的最坏时间复杂度是n2,归并的最好最坏都是nlogn

归并的速度开始超过快速排序了，因为归并排序比快排要稳定，所以在数据量大的时候，快排容易达到 O (n^2) 的时间复杂度，所以大量数据二路归并排序是更好的选择