排序算法总结 java实现

骑猪看日落 2022-05-28 03:22 195阅读 0赞

import java.util.Arrays;  
  
  
public class SortTest \{  
  
  
public static void main(String\[\] args) \{  
// TODO Auto-generated method stub  
int\[\] a = \{13,25,61,34,6,74,2,12,1,36,7,3\};  
for(int num:a)  
System.out.print(num+" ");  
System.out.println();  
/\*\*  
\* 冒泡测试  
\*/  
int\[\] bubbleSortArr = bubbleSort(Arrays.copyOf(a, a.length));  
for(int num:bubbleSortArr)  
System.out.print(num+" ");  
System.out.println();  
/\*\*  
\* 选排测试  
\*/  
int\[\] selectionSortArr = selectionSort(Arrays.copyOf(a, a.length));  
for(int num:selectionSortArr)  
System.out.print(num+" ");  
System.out.println();  
/\*\*  
\* 插排测试  
\*/  
int\[\] insertSortArr = insertionSort(Arrays.copyOf(a, a.length));  
for(int num:insertSortArr)  
System.out.print(num+" ");  
System.out.println();  
/\*\*  
\* 希尔测试：略  
\* 归并测试：略  
\*/  
  
/\*\*  
\* 快排测试：  
\*/  
int\[\] quickSortArr = Arrays.copyOf(a, a.length);  
quickSort(quickSortArr, 0, quickSortArr.length-1);  
for(int num:quickSortArr)  
System.out.print(num+" ");  
System.out.println();

![70][]

/\*\*  
\* 冒泡排序：  
\* 1比较相邻的元素。如果第一个比第二个大，就交换它们两个；  
   2对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；  
     3针对所有的元素重复以上的步骤，除了最后一个；  
        重复步骤1~3，直到排序完成。  
\* @param arr  
\*/  
public static int\[\] bubbleSort(int\[\] arr)\{  
for(int i=0;i<arr.length;i++)\{//i只是趟数，不参与比较  
for(int j=0;j<arr.length-1-i;j++)\{//比较j和j+1 所以要-1  
if(arr\[j\]>arr\[j+1\])\{  
int temp = arr\[j+1\];  
arr\[j+1\]=arr\[j\];  
arr\[j\]=temp;  
\}  
\}  
\}  
return arr;  
\}  
/\*\*  
\* 选择排序：  
\* n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：  
  
  
1.初始状态：无序区为R\[1..n\]，有序区为空；  
2.第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R\[1..i-1\]和R(i..n）。  
     该趟排序从当前无序区中-选出关键字最小的记录 R\[k\]，将它与无序区的第1个记录R交换，  
     使R\[1..i\]和R\[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；  
3.n-1趟结束，数组有序化了。  
\* @param arr  
\*/  
public static int\[\] selectionSort(int\[\] arr)\{  
int minNumIndex;//保存最小值索引  
for(int i=0;i<arr.length-1;i++)\{  
minNumIndex = i;//首先让有序区第最末一个作为最小值索引  
for(int j=i+1;j<arr.length;j++)\{  
if(arr\[j\]<arr\[minNumIndex\])\{//寻找最小的数  
minNumIndex = j;//将最小数的索引保存  
\}  
\}  
int temp = arr\[i\];  
arr\[i\] = arr\[minNumIndex\];//交换最小值到有序列末尾  
arr\[minNumIndex\]=temp;  
\}  
return arr;  
\}  
  
/\*\*   
\* 插入排序：  
\*  1从第一个元素开始，该元素可以认为已经被排序；  
2取出下一个元素，在已经排序的元素序列中从后向前扫描；  
3如果该元素（已排序）大于新元素，将该元素移到下一位置；  
4重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；  
5将新元素插入到该位置后；  
6重复步骤2~5。  
\* @param arr  
\* @return  
\*/  
public static int\[\] insertionSort(int\[\] arr)\{  
int preIndex,current;  
for(int i=1;i<arr.length;i++)\{//假设第一个有序，向后寻找到最末尾  
preIndex = i-1;//保存已有序的序列最末尾的位置  
current=arr\[i\];  
while(preIndex>=0&&arr\[preIndex\]>current)\{  
arr\[preIndex+1\] = arr\[preIndex\];  
preIndex--;  
\}  
arr\[preIndex+1\] = current;  
\}  
return arr;  
\}  
/\*\*  
\* 希尔排序：  
\* 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：  
  
  
1选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；  
2按增量序列个数k，对序列进行k 趟排序；  
3每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。  
   仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。  
\*/  
  
/\*\*  
\* 归并排序：  
\* 把长度为n的输入序列分成两个长度为n/2的子序列；  
对这两个子序列分别采用归并排序；  
将两个排序好的子序列合并成一个最终的排序序列。  
\*/  
  
/\*\*  
\* 快速排序  
\*   
\*   
\*

\*/

![70 1][]

public static void quickSort(int\[\] a, int left, int right)\{    
          
        int i,j,jizhunshu;     
            
        if(left>right)//左指针必须小于右指针     
        return;     
                                        
        jizhunshu=a\[left\]; //jizhunshu中存的就是基准数     
        i=left;  //左哨兵    
        j=right; //右哨兵    
            
        while(i!=j)\{     
        //顺序很重要，要先从右边开始找     
        while(a\[j\]>=jizhunshu && i<j)//从右向左找小于基准数的值     
        j--;     
            //再找左边  
            while(a\[i\]<=jizhunshu && i<j)//从左向右找大于基准数的值  
            i++;     
            //交换两个数在数组中的位置     
            if(i<j)\{     
                int t=a\[i\];     
                a\[i\]=a\[j\];     
                a\[j\]=t;     
            \}     
        \}     
        //最终将基准数归位     
        a\[left\]=a\[i\];     
        a\[i\]=jizhunshu;   //此时left和right值不变  
                                     
        quickSort(a,left,i-1);//继续处理左边的，这里是一个递归的过程     
        quickSort(a,i+1,right);//继续处理右边的 ，这里是一个递归的过程        
    \}    
/\*\*  
\* 堆排序：  
\* 建立大/小顶堆，自下而上找顺序，不符合交换，然后逐层上翻  
\*/  
\}

[70]: /images/20220528/e20501be2b114e80bdd7d8afd4679fda.png
[70 1]: /images/20220528/55e8ff58a69d450497a45bdb685facc5.png