关于数据结构中的几种排序以及相关代码实现

- 日理万妓 2022-05-12 03:16 96阅读 0赞

> ## 目录结构以及排序算法比较： ##
> 
>         
> 
> ![70][]
> 
> ![70 1][]
> 
> 1.  ### 插入排序 ###
>     
>     1.  概念：  
>             插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
>     2.  分类：
>         
>         1.  直接插入排序  
>                 直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列  
>                 **代码实现**
>             
>                 public void insertSort(int[] array){
>                 for(int i=1;i<array.length;i++)
>                 //第0位独自作为有序数列，从第1位开始向后遍历
>                         {
>                             if(array[i]<array[i-1])
>                 //0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
>                             {
>                                 int temp=array[i];//保存第i位的值
>                                 int k = i - 1;
>                                 for(int j=k;j>=0 && temp<array[j];j--)
>                 //从第i-1位向前遍历并移位，直至找到小于第i位值停止
>                                 {
>                                     array[j+1]=array[j];
>                                     k--;
>                                 }
>                                 array[k+1]=temp;//插入第i位的值
>                             }
>                         } 
>                     }
>         2.  折半插入排序（二分插入排序）  
>                 将直接插入排序中寻找A\[i\]的插入位置的方法改为采用折半比较，即可得到折半插入排序算法  
>             **    实施步骤  
>                     第一步：二分法查找插入位置  
>                     第二步：后移  
>                     第三步：插入  
>                 代码实现  
>              **
>             
>                 public static void advanceInsertSortWithBinarySearch(int[] arr) {
>                     for (int i = 1; i < arr.length; i++) {
>                         int temp = arr[i];
>                         int low = 0, high = i - 1;
>                         int mid = -1;
>                         while (low <= high) {            
>                             mid = low + (high - low) / 2;            
>                             if (arr[mid] > temp) {               
>                                 high = mid - 1;            
>                             } else { // 元素相同时，也插入在后面的位置                
>                                 low = mid + 1;            
>                             }        
>                         }        
>                         for(int j = i - 1; j >= low; j--) {            
>                             arr[j + 1] = arr[j];        
>                         }        
>                         arr[low] = temp;    
>                     }
>                 }
>     3.  描述：
>         
>         一般来说，插入排序都采用in-place在[数组][Link 1]上实现。具体算法描述如下：
>         
>         ⒈ 从第一个元素开始，该元素可以认为已经被排序
>         
>         ⒉ 取出下一个元素，在已经排序的元素序列中从后向前扫描
>         
>         ⒊ 如果该元素（已排序）大于新元素，将该元素移到下一位置
>         
>         ⒋ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
>         
>         ⒌ 将新元素插入到下一位置中
>         
>         ⒍ 重复步骤2~5  
>             如果比较操作的代价比交换操作大的话，可以采用[二分查找][Link 2]法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为[二分查找][Link 2]排序
> 2.  ### 选择排序 ###
>     
>     1.  概念：  
>             选择排序（Selection sort）是一种简单直观的[排序算法][Link 3]。它的工作原理是每一次从待排序的[数据元素][Link 4]中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
>     2.  分类：
>         
>         1.  堆排序  
>             堆排序(Heapsort)是指利用堆积树（堆）这种[数据结构][Link 5]所设计的一种[排序算法][Link 3]，它是选择排序的一种
>         2.  直接选择排序
>             
>             1.  基本思想：  
>                     第一次从R\[0\]~R\[n-1\]中选取最小值，与R\[0\]交换，第二次从R\[1\]~R\[n-1\]中选取最小值，与R\[1\]交换，....，第i次从R\[i-1\]~R\[n-1\]中选取最小值，与R\[i-1\]交换，.....，第n-1次从R\[n-2\]~R\[n-1\]中选取最小值，与R\[n-2\]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列
>             2.  代码实现：
>                 
>                     void SelectSort(elemtype R[], int n) {
>                         	int i, j, m;
>                         	elemtype t;
>                         	for (i = 0; i < n - 1; i++) {
>                          	   	m = i;
>                            	 	for (j = i + 1; j < n; j++)
>                              	if (R[j] < R[m]) m = j;
>                             	if (m != i) {
>                                 	t = R[i];
>                                 	R[i] = R[m];
>                                 	R[m] = t;
>                             	}
>                         	}
>                     }
>     3.  代码实现：
>         
>             public static void selectSort(int[]a)
>             {
>                 int minIndex=0;
>                 int temp=0;
>                 if((a==null)||(a.length==0))
>                     return;
>                 for(int i=0;i<a.length-1;i++)
>                 {
>                     minIndex=i;//无序区的最小数据数组下标
>                     for(int  j=i+1;j<a.length;j++)
>                     {
>                         //在无序区中找到最小数据并保存其数组下标
>                         if(a[j]<a[minIndex])
>                         {
>                             minIndex=j;
>                         }
>                     }
>                     //将最小元素放到本次循环的前端
>                     temp=a[i];
>                     a[i]=a[minIndex];
>                     a[minIndex]=temp;
>                 }
>             }
>         
>          
> 3.  ### 交换排序 ###
>     
>     1.  分类：
>         
>         1.  冒泡排序
>             
>             1.  基本原理  
>                     1.比较相邻的元素，如果第一个比第二个大，则交换他们两个  
>                     2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数  
>                     3.针对所有的元素重复以上的步骤，除了最后一个  
>                     4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
>             2.  代码实现：
>                 
>                     public static void bubbleSort(int []arr) {
>                         int[] arr = {12,23,34,56,56,56,78};
>                         for(int i =0;i<arr.length-1;i++) { 
>                             for(int j=0;j<arr.length-i-1;j++) {//-1为了防止溢出
>                                 if(arr[j]>arr[j+1]) {
>                                     int temp = arr[j];      
>                                     arr[j]=arr[j+1];       
>                                     arr[j+1]=temp;
>                                 }
>                             }    
>                         }
>                     }
>         2.  快速排序
>             
>             1.  基本思想：  
>                     通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以[递归][Link 6]进行，以此达到整个数据变成有序[序列][Link 7]
>             2.  代码实现
>                 
>                     public　void　sort(int　arr[],int　low,int　high) {
>                         int　l=low;
>                     　	int　h=high;
>                     　	int　povit=arr[low];
>                     　	while(l<h) {
>                     　		while(l<h&&arr[h]>=povit)
>                     　			h--;
>                     　		if(l<h) {
>                     　			int　temp=arr[h];
>                     　			arr[h]=arr[l];
>                     　			arr[l]=temp;
>                     　			l++;
>                     　		}
>                     　		while(l<h&&arr[l]<=povit)
>                     　			l++;
>                      
>                     　		if(l<h) {
>                     　			int　temp=arr[h];
>                     　			arr[h]=arr[l];
>                     　			arr[l]=temp;
>                     　			h--;
>                     　		}
>                     　	}
>                     　	print(arr);
>                     　	System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
>                     　	if(l>low)
>                             sort(arr,low,l-1);
>                     　	if(h<high)
>                             sort(arr,l+1,high);
>                     　}
>                 
>                  
> 4.  ### 归并排序 ###
>     
>     1.  概念原理  
>             归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 8]
>         
>             归并操作的工作原理如下：
>         
>                 第一步：申请空间，使其大小为两个已经[排序][Link 9]序列之和，该空间用来存放合并后的序列
>         
>                 第二步：设定两个[指针][Link 10]，最初位置分别为两个已经排序序列的起始位置
>         
>                 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
>         
>                 重复步骤3直到某一指针超出序列尾
>         
>                将另一序列剩下的所有元素直接复制到合并序列尾
>     2.  比较
>         
>         归并[排序][Link 9]是稳定的排序.即相等的元素的顺序不会改变
>         
>         归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数
>         
>         速度仅次于[快速排序][Link 11]，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的[数列][Link 12]
>     3.  代码实现  
>          
>         
>             public class MergeSort {
>                 /**
>                  * 　*　<pre>
>                  * 　*　二路归并
>                  * 　*　原理：将两个有序表合并和一个有序表
>                  * 　*　</pre>
>                  * 　*
>                  * 　*　@param　a
>                  * 　*　@param　s
>                  * 　*　第一个有序表的起始下标
>                  * 　*　@param　m
>                  * 　*　第二个有序表的起始下标
>                  * 　*　@param　t
>                  * 　*　第二个有序表的结束下标
>                  * 　*
>                  */
>                 private static void merge(int[] a, int s, int m, int t) {
>                     int[] tmp = new int[t - s + 1];
>                     int i = s, j = m, k = 0;
>                     while (i < m && j <= t) {
>                         if (a[i] <= a[j]) {
>                             tmp[k] = a[i];
>                             k++;
>                             i++;
>                         } else {
>                             tmp[k] = a[j];
>                             j++;
>                             k++;
>                         }
>                     }
>                     while (i < m) {
>                         tmp[k] = a[i];
>                         i++;
>                         k++;
>                     }
>                     while (j <= t) {
>                         tmp[k] = a[j];
>                         j++;
>                         k++;
>                     }
>                     System.arraycopy(tmp, 0, a, s, tmp.length);
>                 }
>              
>                 /**
>                  * 　*　每次归并的有序集合的长度
>                  */
>                 public static void mergeSort(int[] a, int s, int len) {
>                     int size = a.length;
>                     int mid = size / (len << 1);
>                     int c = size & ((len << 1) - 1);
>                     //　-------归并到只剩一个有序集合的时候结束算法-------//
>                     if (mid == 0)
>                         return;
>                     //　------进行一趟归并排序-------//
>                     for (int i = 0; i < mid; ++i) {
>                         s = i * 2 * len;
>                         merge(a, s, s + len, (len << 1) + s - 1);
>                     }
>                     //　-------将剩下的数和倒数一个有序集合归并-------//
>                     if (c != 0)
>                         merge(a, size - c - 2 * len, size - c, size - 1);
>                     //　-------递归执行下一趟归并排序------//
>                     mergeSort(a, 0, 2 * len);
>                 }
>              
>                 public static void main(String[] args) {
>                     int[] a = new int[]{4, 3, 6, 1, 2, 5};
>                     mergeSort(a, 0, 1);
>                     for (int i = 0; i < a.length; ++i) {
>                         System.out.print(a[i] + "　");
>                     }
>                 }
>             }
>         
>          
> 5.  ### 基数排序 ###
>     
>     1.  概念原理：  
>             将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
>     2.  代码实现：
>         
>             public class RadixSort {
>                 public static void sort(int[] number, int d) {
>                     intk = 0;
>                     intn = 1;
>                     intm = 1; 
>                     int[][]temp = newint[10][number.length]; 
>                     int[]order = newint[10];
>                     while(m <= d) { 
>             
>                         for(inti = 0; i < number.length; i++) {
>                             intlsd = ((number[i] / n) % 10);
>                             temp[lsd][order[lsd]] = number[i];
>                             order[lsd]++;
>                         }
>             
>                         for(inti = 0; i < 10; i++) {
>                             if(order[i] != 0)
>                                 for(intj = 0; j < order[i]; j++) {
>                                     number[k] = temp[i][j];
>                                     k++;
>                                 }
>                             order[i] = 0;
>                         }
>             
>                         n *= 10;
>                         k = 0;
>                         m++;
>                     }
>                 }
>             }
>         
>

> ##  备注：参考文献来自相关博客以及百度百科，技术小白，如有错误还望指正 ##

[70]: /images/20220512/6c9c5566fedb43548c4b99c06ba1f4d8.png
[70 1]: /images/20220512/f99ad050c14347879b84b7b2c8992ee7.png
[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E7%BB%84
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE
[Link 3]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605
[Link 4]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 5]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 6]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695
[Link 7]: https://baike.baidu.com/item/%E5%BA%8F%E5%88%97/1302588
[Link 8]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741
[Link 9]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F
[Link 10]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88
[Link 11]: https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
[Link 12]: https://baike.baidu.com/item/%E6%95%B0%E5%88%97