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

悠悠 2022-01-11 05:17 402阅读 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;iarray[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;iarray[j+1]){ //从大到小，或者从小到大
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
isSort = false;
count++;
} 

  1.         \}  
  2.         if(isSort)\{  
  3.             break;  
  4.         \}  
  6.     \}  
  7.     System.out.println("循环次数"+count);  
  8. \}  
  9. /\*\*  
  10.  \* 选择排序  
  11.  \* 双层循环，时间复杂度和冒泡一模一样，都是O(n2)  
  12.  \* 不稳定  
  13.  \* 算法思想：初始化第一个i为最小值，然后找到序列中的最小值与第一个i进行交换，依次找到最小的元素，  
  14.  \*       进行双层for循环，i=0到length；初始化最小元素的下标。j=i+到length，依次比较大小，将最小元素下标进行更新，在i循环层进行交换位置  
  15.  \*/  
  16. public static void selectSort(int array\[\])\{  //选择最小的数字放在最左或者最右
  18.     for(int i=0;i<array.length;i++)\{  
  19.         int min = i;  
  20.         for(int j=i+1;j<array.length;j++)\{  
  21.             if(array\[j\]<array\[min\])\{   //找到最小的元素  
  22.                 min = j;  
  23.             \}  
  24.         \}  
  25.         int tempt = array\[i\];      //最小的元素与第i个元素进行位置的交换  
  26.         array\[i\] = array\[min\];  
  27.         array\[min\] = tempt;  
  28.     \}  
  29. \}  
  30. /\*\*  
  31.  \* 插入排序  
  32.  \* 稳定，简单  
  33.  \* 算法思想：数组分为两个区域，一个已排序，一个未排序，初始化中已排序为空，第一轮，取出第一个数，然后插入到已排序区域中，此时已排序为空，就不做比较。  
  34.  \*       第二轮继续将未排序数组拿出一个，插入到已排序区域中，挨个遍历比较，然后进行排序交换。依次循环  
  35.  \*  最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)  
  36.  \*/  
  37. public static void insertSort(int array\[\])\{  //选择最小的数字放在最左或者最右  
  38.     //  
  39.     for(int i=1;i<array.length;i++)\{  
  40.         int value = array\[i\];  
  41.         int j=0;  
  42.         for(j=i-1;j>=0;j--)\{  
  43.             if(array\[j\]>value)\{  
  44.                 array\[j+1\] = array\[j\];  //移动元素，将需要插入的元素，插入到已经排序的数组中，所以是从i-1到0进行插入比较  
  45.             \}else\{  
  46.                 break; //找到合适的位置不需要再进行比较  
  47.             \}  
  48.         \}  
  49.         array\[j+1\] = value;  
  50.         System.out.println("array\[j+1\] "+array\[j+1\]);  
  51.     \}  
  52. \}  
  53. /\*\*  
  54.  \* 希尔排序  
  55.  \* 最好情况的时间复杂度是 O(n)，最坏情况的时间复杂度是 O(n2)  
  56.  \* 不稳定，复杂，  
  57.  \* 算法思想：插入排序的高级版本，插入排序对于大规模的乱序数组的时候效率较低，每次只移动一位，希尔排序可以快速插入，跳跃移动数据  
  58.  \*       设置排序区间，例如设置为4，则首先将第五个数据与第一个数据比较，然后交换，指针右移动，第6个数据与第二个数据比较。依次右移指针，进行比较，  
  59.  \*       如果交换数据后，发现减去区间得到的位置还存在数据，那么继续进行比较。当最后一个元素比较完之后，较大的数据大多调整到数组后半部分。  
  60.  \*       然后缩小去京，进行比较，直到区间缩小到1；区间为1的时候，也就是插入排序。  
  61.  \*/  
  62. public static void hillSort(int array\[\])\{    
  63.     int length = array.length;  
  64.     //设置区间  
  65.     int interval = 1;  
  66.     while(interval < length)\{  
  67.         interval = interval\*3 + 1;  //设置区间 4  
  68.     \}  
  70.     while(interval > 0)\{  
  71.         for(int i=interval;i<length;i++)\{ //区间后一部分的数据  
  72.             int j = i-interval;  //区间前一部分的数据  
  73.             int temp = array\[i\];  
  74.             while(j>=0 && array\[j\] > temp)\{  
  75.                 //跨区间循环  
  76.                 array\[j+interval\] = array\[j\]; //转换过程想要根据interval的值进行变换，所以下标值都需要采用interval进行转换  
  77.                 j = j - interval;            //为下一步根据区间赋值做准备  
  78.                 //System.out.println("j: "+j);  
  79.             \}  
  80.             array\[j+interval\] = temp;   //更改array\[j\]的值  
  81.         \}  
  82.         interval = interval / 3;  //更新区间大小  4,  1,  0  
  83.         //System.out.println("interval "+interval);  
  84.     \}  
  85. \}  
  86. /\*\*  
  87.  \* 归并排序  
  88.  \* 时间复杂度，O(N\*log2N)  较为稳定，也较为复杂  
  89.  \* 归并排序每次递归都要用到一个辅助表，长度与待排序的表长度相同，虽然递归次数是O(log2n)，但每次递归都会释放掉所占的辅助空间，  
  90.  \* n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。  
  91.  \* 算法思想：主要采用分治的思想，将数组一分两半，递归切分，直到切分到单个元素，然后进行重新排序组合。  
  92.  \*       需要数据量较小的情况  
  93.  \*/  
  94. public static void mergeSort(int array\[\])\{    
  95.     int temparray\[\] = new int\[array.length\];  
  96.     mSort(array, temparray, 0, array.length-1);  
  97. \}  
  98. public static void mSort(int array\[\], int temparray\[\],int start, int end)\{    
  99.     if(start >= end)\{  //start >= end 等于号，切分到单个元素  
  100.         return;  
  101.     \}  
  102.     int middle =start + (end - start) /2;  //每个小数组的中间值，需要考虑start  
  103.     //分解数组  
  104.     mSort(array, temparray, start, middle);  
  105.     mSort(array, temparray, middle+1, end);  
  106.     //合并  
  107.     merge(array, temparray, start, end, middle);  
  108. \}  
  109. public static void merge(int array\[\], int temparray\[\],int start, int end, int middle)\{  
  110.     for(int i = start;i<=end;i++)\{  
  111.         temparray\[i\] = array\[i\];   //对原来的数组进行复制，首先复制的是单个元素，然后逐渐合并为小数组  
  112.     \}  
  113.     int left = start;  
  114.     int right = middle + 1;  
  116.     for(int j=start;j<=end;j++)\{  
  117.         if(left > middle)\{   //左边数据排序完成  
  118.             array\[j\] = temparray\[right++\];  
  119.         \}else if(right > end)\{  //右边数据排序完成  
  120.             array\[j\] = temparray\[left++\];  
  121.         \}else if(temparray\[right\] < temparray\[left\])\{ //右边的首位排入进来，右边下标进行+1  
  122.             array\[j\] = temparray\[right++\];  
  123.         \}else\{     //左边的首位排入进来，左边下标进行+1  
  124.             array\[j\] = temparray\[left++\];  
  125.         \}  
  126.     \}  
  127. \}  
  128. /\*\*  
  129.  \* 测试相关算法  
  130.  \* @author ycy  
  131.  \*/  
  132. public static void main(String\[\] args) \{  
  133.     // TODO Auto-generated method stub  
  134.     int array\[\] = \{5,7,3,2\};  
  135.     for(int i=0;i<array.length;i++)\{  
  136.         System.out.print(array\[i\] + " ");  
  137.     \}  
  138.     System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
  139.     bubbleSort(array);  
  140.     //测试改进冒泡排序，这个需要数据较多情况下，能够看到效果  
  141.     int array1\[\] = \{5,7,3,2\};  
  142.     improvebubbleSort(array1);  
  143.     for(int i=0;i<array.length;i++)\{  
  144.         System.out.print(array\[i\] + " ");  
  145.     \}  
  146.     //测试插入排序  
  147.     System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
  148.     int array2\[\] = \{5,7,3,2\};  
  149.     insertSort(array2);  
  150.     for(int i=0;i<array2.length;i++)\{  
  151.         System.out.print(array2\[i\] + " ");  
  152.     \}  
  153.     //测试希尔排序  
  154.     System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
  155.     int array3\[\] = \{5,7,3,2,1,4,6,9,8,10\};  
  156.     hillSort(array3);  
  157.     for(int i=0;i<array3.length;i++)\{  
  158.         System.out.print(array3\[i\] + " ");  
  159.     \}  
  160.     //测试归并排序  
  161.     System.out.println("\*\*\*\*\*\*\*\*\*\*\*\*\*\*");  
  162.     int array4\[\] = \{5,7,3,2,1,4,6,9,8,10\};  
  163.     mergeSort(array4);  
  164.     for(int i=0;i<array4.length;i++)\{  
  165.         System.out.print(array4\[i\] + " ");  
  166.     \}  
  167. \}

}

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

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70

发表评论

表情：
评论列表 （有 0 条评论，402人围观）

还没有评论，来说两句吧...

相关阅读