冒泡排序、选择排序、插入排序、希尔排序、归并排序-Java基础

悠悠 2022-01-11 05:17 346阅读 0赞

** \* 1. 传统的冒泡排序**

\* 时间复杂度为O(n2) 最好情况为o(n)

\* 特点：1、冒泡排序是一种用时间换空间的排序方法，n小的时候好

\* 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级

3、最好的情况是数据本来就有序，复杂度为O(n)

\* 冒泡的思想：从序列的一端到另一端一直进行冒泡，依次比较相邻的两个数的大小，如果不符合要排序的进行交换。、

\*      双层for循环，i=0到length\-1；j=0到length\-i\-1，依次比较大小进行交换位置

//2. 改进的冒泡排序

** \* 3. 选择排序**

\* 双层循环，时间复杂度和冒泡一模一样，都是O(n2)

\* 不稳定

\* 算法思想：初始化第一个i为最小值，然后找到序列中的最小值与第一个i进行交换，依次找到最小的元素，

\*  进行双层for循环，i=0到length；初始化最小元素的下标。j=i+到length，依次比较大小，将最小元素下标进行更新，在i循环层进行交换位置

** \* 4. 插入排序**

\* 稳定，简单

\* 算法思想：数组分为两个区域，一个已排序，一个未排序，初始化中已排序为空，第一轮，取出第一个数，然后插入到已排序区域中，此时已排序为空，就不做比较。

\*       第二轮继续将未排序数组拿出一个，插入到已排序区域中，挨个遍历比较，然后进行排序交换。依次循环

\*  最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)

** \* 5. 希尔排序**

\* 最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)

\* 不稳定，复杂，

\* 算法思想：插入排序的高级版本，插入排序对于大规模的乱序数组的时候效率较低，每次只移动一位，希尔排序可以快速插入，跳跃移动数据

\*       设置排序区间，例如设置为4，则首先将第五个数据与第一个数据比较，然后交换，指针右移动，第6个数据与第二个数据比较。依次右移指针，进行比较，

\*       如果交换数据后，发现减去区间得到的位置还存在数据，那么继续进行比较。当最后一个元素比较完之后，较大的数据大多调整到数组后半部分。

\*       然后缩小去京，进行比较，直到区间缩小到1；区间为1的时候，也就是插入排序。

**\*** **6. 归并排序**

\* 时间复杂度，O(N\*log2N)  较为稳定，也较为复杂

\* 归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，

\* n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。

\* 算法思想：主要采用分治的思想，将数组一分两半，递归切分，直到切分到单个元素，然后进行重新排序组合。

\*       需要数据量较小的情况

package pratice618;

public class testBubbleSort \{  
    /\*\*  
     \* @param ycy  
     \* 多种排序算法的代码实现和说明  
     \*/  
    /\*\*  
     \* 传统的冒泡排序  
     \* 时间复杂度为O(n2) 最好情况为o(n)  
     \* 特点：   1、冒泡排序是一种用时间换空间的排序方法，n小的时候好  
      \*        2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级  
            3、最好的情况是数据本来就有序，复杂度为O(n)  
     \* 冒泡的思想：从序列的一端到另一端一直进行冒泡，依次比较相邻的两个数的大小，如果不符合要排序的进行交换。、  
     \*        双层for循环，i=0到length-1；j=0到length-i-1，依次比较大小进行交换位置  
     \*/  
    public static void bubbleSort(int array\[\])\{  //传统的冒泡排序，时间复杂度为O(n2)  
        int count=0;  
        for(int i=0;i<array.length-1;i++)\{      //冒泡轮数  
            for(int j=0;j<array.length-1-i;j++)\{  //依次比较的次数  
                int temp=0;  
                if(array\[j\]>array\[j+1\])\{      //从大到小，或者从小到大  
                    temp = array\[j\];  
                    array\[j\] = array\[j+1\];  
                    array\[j+1\] = temp;  
                    count++;  
                \}  
            \}  
        \}  
        System.out.println("循环次数"+count);  
    \}  
    //改进的冒泡排序  
    public static void improvebubbleSort(int array\[\])\{  //临时遍历来标记该数组是否已经有序  
        int count=0;  
        for(int i=0;i<array.length-1;i++)\{      //冒泡轮数  
            boolean isSort = true;  
            for(int j=0;j<array.length-1-i;j++)\{  //依次比较的次数  
                int temp=0;  
                if(array\[j\]>array\[j+1\])\{      //从大到小，或者从小到大  
                    temp = array\[j\];  
                    array\[j\] = array\[j+1\];  
                    array\[j+1\] = temp;  
                    isSort = false;  
                    count++;  
                \}  
                  
            \}  
            if(isSort)\{  
                break;  
            \}  
              
        \}  
        System.out.println("循环次数"+count);  
    \}  
    /\*\*  
     \* 选择排序  
     \* 双层循环，时间复杂度和冒泡一模一样，都是O(n2)  
     \* 不稳定  
     \* 算法思想：初始化第一个i为最小值，然后找到序列中的最小值与第一个i进行交换，依次找到最小的元素，  
     \*       进行双层for循环，i=0到length；初始化最小元素的下标。j=i+到length，依次比较大小，将最小元素下标进行更新，在i循环层进行交换位置  
     \*/  
    public static void selectSort(int array\[\])\{  //选择最小的数字放在最左或者最右

for(int i=0;i<array.length;i++)\{  
            int min = i;  
            for(int j=i+1;j<array.length;j++)\{  
                if(array\[j\]<array\[min\])\{   //找到最小的元素  
                    min = j;  
                \}  
            \}  
            int tempt = array\[i\];      //最小的元素与第i个元素进行位置的交换  
            array\[i\] = array\[min\];  
            array\[min\] = tempt;  
        \}  
    \}  
    /\*\*  
     \* 插入排序  
     \* 稳定，简单  
     \* 算法思想：数组分为两个区域，一个已排序，一个未排序，初始化中已排序为空，第一轮，取出第一个数，然后插入到已排序区域中，此时已排序为空，就不做比较。  
     \*       第二轮继续将未排序数组拿出一个，插入到已排序区域中，挨个遍历比较，然后进行排序交换。依次循环  
     \*  最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)  
     \*/  
    public static void insertSort(int array\[\])\{  //选择最小的数字放在最左或者最右  
        //  
        for(int i=1;i<array.length;i++)\{  
            int value = array\[i\];  
            int j=0;  
            for(j=i-1;j>=0;j--)\{  
                if(array\[j\]>value)\{  
                    array\[j+1\] = array\[j\];  //移动元素，将需要插入的元素，插入到已经排序的数组中，所以是从i-1到0进行插入比较  
                \}else\{  
                    break; //找到合适的位置不需要再进行比较  
                \}  
            \}  
            array\[j+1\] = value;  
            System.out.println("array\[j+1\] "+array\[j+1\]);  
        \}  
    \}  
    /\*\*  
     \* 希尔排序  
     \* 最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)  
     \* 不稳定，复杂，  
     \* 算法思想：插入排序的高级版本，插入排序对于大规模的乱序数组的时候效率较低，每次只移动一位，希尔排序可以快速插入，跳跃移动数据  
     \*       设置排序区间，例如设置为4，则首先将第五个数据与第一个数据比较，然后交换，指针右移动，第6个数据与第二个数据比较。依次右移指针，进行比较，  
     \*       如果交换数据后，发现减去区间得到的位置还存在数据，那么继续进行比较。当最后一个元素比较完之后，较大的数据大多调整到数组后半部分。  
     \*       然后缩小去京，进行比较，直到区间缩小到1；区间为1的时候，也就是插入排序。  
     \*/  
    public static void hillSort(int array\[\])\{    
        int length = array.length;  
        //设置区间  
        int interval = 1;  
        while(interval < length)\{  
            interval = interval\*3 + 1;  //设置区间 4  
        \}  
          
        while(interval > 0)\{  
            for(int i=interval;i<length;i++)\{ //区间后一部分的数据  
                int j = i-interval;  //区间前一部分的数据  
                int temp = array\[i\];  
                while(j>=0 && array\[j\] > temp)\{  
                    //跨区间循环  
                    array\[j+interval\] = array\[j\]; //转换过程想要根据interval的值进行变换，所以下标值都需要采用interval进行转换  
                    j = j - interval;            //为下一步根据区间赋值做准备  
                    //System.out.println("j: "+j);  
                \}  
                array\[j+interval\] = temp;   //更改array\[j\]的值  
            \}  
            interval = interval / 3;  //更新区间大小  4,  1,  0  
            //System.out.println("interval "+interval);  
        \}  
    \}  
    /\*\*  
     \* 归并排序  
     \* 时间复杂度，O(N\*log2N)  较为稳定，也较为复杂  
     \* 归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，  
     \* n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。  
     \* 算法思想：主要采用分治的思想，将数组一分两半，递归切分，直到切分到单个元素，然后进行重新排序组合。  
     \*       需要数据量较小的情况  
     \*/  
    public static void mergeSort(int array\[\])\{    
        int temparray\[\] = new int\[array.length\];  
        mSort(array, temparray, 0, array.length-1);  
    \}  
    public static void mSort(int array\[\], int temparray\[\],int start, int end)\{    
        if(start >= end)\{  //start >= end 等于号，切分到单个元素  
            return;  
        \}  
        int middle =start + (end - start) /2;  //每个小数组的中间值，需要考虑start  
        //分解数组  
        mSort(array, temparray, start, middle);  
        mSort(array, temparray, middle+1, end);  
        //合并  
        merge(array, temparray, start, end, middle);  
    \}  
    public static void merge(int array\[\], int temparray\[\],int start, int end, int middle)\{  
        for(int i = start;i<=end;i++)\{  
            temparray\[i\] = array\[i\];   //对原来的数组进行复制，首先复制的是单个元素，然后逐渐合并为小数组  
        \}  
        int left = start;  
        int right = middle + 1;  
          
        for(int j=start;j<=end;j++)\{  
            if(left > middle)\{   //左边数据排序完成  
                array\[j\] = temparray\[right++\];  
            \}else if(right > end)\{  //右边数据排序完成  
                array\[j\] = temparray\[left++\];  
            \}else if(temparray\[right\] < temparray\[left\])\{ //右边的首位排入进来，右边下标进行+1  
                array\[j\] = temparray\[right++\];  
            \}else\{     //左边的首位排入进来，左边下标进行+1  
                array\[j\] = temparray\[left++\];  
            \}  
        \}  
    \}  
    /\*\*  
     \* 测试相关算法  
     \* @author ycy  
     \*/  
    public static void main(String\[\] args) \{  
        // TODO Auto-generated method stub  
        int array\[\] = \{5,7,3,2\};  
        for(int i=0;i<array.length;i++)\{  
            System.out.print(array\[i\] + " ");  
        \}  
        System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
        bubbleSort(array);  
        //测试改进冒泡排序，这个需要数据较多情况下，能够看到效果  
        int array1\[\] = \{5,7,3,2\};  
        improvebubbleSort(array1);  
        for(int i=0;i<array.length;i++)\{  
            System.out.print(array\[i\] + " ");  
        \}  
        //测试插入排序  
        System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
        int array2\[\] = \{5,7,3,2\};  
        insertSort(array2);  
        for(int i=0;i<array2.length;i++)\{  
            System.out.print(array2\[i\] + " ");  
        \}  
        //测试希尔排序  
        System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
        int array3\[\] = \{5,7,3,2,1,4,6,9,8,10\};  
        hillSort(array3);  
        for(int i=0;i<array3.length;i++)\{  
            System.out.print(array3\[i\] + " ");  
        \}  
        //测试归并排序  
        System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
        int array4\[\] = \{5,7,3,2,1,4,6,9,8,10\};  
        mergeSort(array4);  
        for(int i=0;i<array4.length;i++)\{  
            System.out.print(array4\[i\] + " ");  
        \}  
    \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20220111/3a627c6b541c4ab5979e755d2e190c67.png