Java排序算法总结

发表于 更新于 分类于 阅读次数： Valine： 

        

        
        



十大排序.png


冒泡排序
算法描述：  


冒泡排序：依次比较左右相邻的元素，若前一元素大于后一元素则相互交换，直到最后一个元素为最大元素。重复之前操作，直到倒数第二个元素为次最大元素，以此类推。


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 冒泡排序
 * 时间复杂度：O(N平方)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * 备注：n较小的情况使用
 * @author Philstar
 */
package SortingMethod;

public class bubbleSort {
    public static void main(String[] args) {
        int[] arr={25,5,7,8,4,1};
        BubbleSort(arr);
    }
    public static void BubbleSort(int[] arr){
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        for(int x:arr)
            System.out.print(x+" ");
    }
}





选择排序
算法描述：  


选择排序的基本思想：首先初始化最小元素索引值为首元素，依次遍历带排序数列，当遇到小于该元素的值后将最小元素索引值改为当前元素的索引值，直到遇到尾元素，结束遍历，并将最小索引处元素与首元素交换。然后将第二位元素初始化为最小索引值，同样的操作，使得第二位元素位次最小元素。以此类推。


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 选择排序
 * 时间复杂度：O(N平方)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * 备注：n较小的情况使用
 * @author Philstar
 */
package SortingMethod;

public class chooseSort {
    public static void main(String[] args) {
        int[] arr={25,5,7,8,4,1};
        ChooseSort(arr);
    }
    public static void ChooseSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int min=arr[i];
            int Min_index=i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<min){
                    min=arr[j];
                    Min_index=j;
                }
            }
            arr[Min_index]=arr[i];
            arr[i]=min;
        }
        for(int x:arr)
            System.out.print(x+" ");
    }
}





快速排序
算法描述：  


快排即是对冒泡排序的一种改进，使用了分治的思想。通过选择一个元素作为pivot，并围绕着选定的pivot划分给定的数组。




quickSort有多种不同的版本：  


    

  1. 始终选择第一个元素作为枢轴。  
    2. 

  2. 始终选择最后一个元素作为枢轴（在下面实现）  
    3. 

  3. 选择一个随机元素作为枢轴。  
    4. 

  4. 选择中位数作为枢轴。
    5. 





quickSort的关键过程是partition(),分区的目标是，给定一个数组和一个数组元素x作为枢轴，将x放在已排序组中的正确位置，并将所有较小的元素（小于x）放在x之前，并将所有较大的元素（大于x）放在之后X。


图片演示：  


qucikSort.png


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 快速排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)
 * 稳定性：不稳定
 * @author Philstar
 */
package SortingMethod;

public class quickSort {
    public static void main(String[] args) {
        int[] arr={10,80,30,90,40,50,70};
        int[] n_arr=QuickSort(arr,0,arr.length-1);
        for(int x:n_arr)
            System.out.print(x+" ");
    }
    public static int[] QuickSort(int[] arr,int low,int high){
        if(low<high){
            int pi=partition(arr,low,high);

            QuickSort(arr,low,pi-1);
            QuickSort(arr,pi+1,high);
        }
        return arr;
    }
    static int partition(int[] arr,int low,int high) {
        int pivot=arr[high];
        int i=(low-1);              //较小元素的索引
        for(int j=low;j<high;j++){
            if(arr[j]<pivot){       //如果当前元素小于pivot
                i++;
                int temp=arr[i];    //交换arr[i]与arr[j]
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
        int temp=arr[i+1];          //交换arr[i+1]与arr[high](pivot)
        arr[i+1]=arr[high];
        arr[high]=temp;
        return i+1;                 //返回pivot当前所在的索引值
    }
}





插入排序
算法描述：  


插入排序（Straight Insertion Sorting）的基本思想：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。


图片演示：  


insertSorting.png


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 插入排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 * 稳定性：稳定
 * @author Philstar
 */
package SortingMethod;

public class StraightInsertingSort {
    public static void main(String[] args) {
        int[] arr={10,80,30,90,40,50,70};
        int[] n_arr=straightInsertingSort(arr);
        for(int x:arr)
            System.out.print(x+" ");
    }
    public static int[] straightInsertingSort(int[] arr){
        int current;
        for(int i=1;i<arr.length;i++){
            current=arr[i];                 //设置当前值
            int j=i-1;                      //待比较的值的索引
            while(j>=0 && current<arr[j]){  //重后往前循环，当遇到比当前值大的数时将该元素向后移一位
                arr[j+1]=arr[j];
                j--;
            }
            arr[j+1]=current;               //找到位置，插入当前元素
        }
        return arr;
    }
}





希尔排序
算法描述：  


希尔排序：是对直接插入排序的一种改进排序算法。希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 希尔排序
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * @author Philstar
 */
package SortingMethod;

public class ShellSort {
    public static void main(String[] args) {
        ShellSort op=new ShellSort();
        int[] arr = {10,80,30,90,40,50,70};
        int[] n_arr = op.shellSort(arr);
        for(int x:n_arr)
            System.out.print(x+" ");
    }
    int[] shellSort(int[] arr){
        for(int gap = arr.length/2;gap > 0;gap /= 2){
            for(int i = gap;i < arr.length; i++){   //从这开始后面都为插入排序，只是将变量改为gap
                int temp = arr[i];
                int j;
                for(j = i;j >= gap && arr[j-gap] > temp;j-=gap)
                    arr[j] = arr[j-gap];
                arr[j] = temp;
            }
        }
        return arr;
    }
}





归并排序
算法描述：
归并排序：与快排一样，归并排序也是使用分治的思想，选择相邻两个数组成一个有序序列,选择相邻的两个有序序列组成一个有序序列,重复第二步，直到全部组成一个有序序列。


图片演示：  


MergeSort.png




动图演示：




mergeSort.gif


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 归并排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 * 要求稳定性时使用
 * @author Philstar
 */
package SortingMethod;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {38,27,43,3,9,82,10};
        MergeSort op = new MergeSort();
        op.sort(arr ,0 ,arr.length-1);
        op.printArr(arr);
    }

    void sort(int arr[], int l, int r){            //分离
        if( l >= r)
            return;
        else{
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m+1, r);

            merge(arr, l, m+1, r);
        }
    }

    void merge(int[] arr, int l, int m, int r){    //合并
        //创建俩个新的数组
        int LEFT_SIZE = m - l;
        int RIGHT_SIZE = r - m + 1;
        int[] left = new int[LEFT_SIZE];
        int[] right = new int[RIGHT_SIZE];
        int i, j, k;
        //将原数组中的元素存入到两个新的数组中
        for(i = l; i < m; i++){
            left[i - l] = arr[i];
        }
        for(j = m; j <= r; j++){
            right[j - m] = arr[j];
        }
        i = 0;
        j = 0;
        k = l;
        //将俩个新数组进行循环比较，将小的元素存入到原数组中
        while( i < LEFT_SIZE && j < RIGHT_SIZE){
            if(left[i] < right[j]){
                arr[k] = left[i];
                i++;
                k++;
            }
            else{
                arr[k] = right[j];
                j++;
                k++;
            }
        }
        //当一个数组已循环完毕，将另一个数组剩余的部分添加至原数组后
        while( i < LEFT_SIZE){
            arr[k] = left[i];
            i++;
            k++;
        }
        while( j < RIGHT_SIZE){
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    void printArr(int [] arr){          //打印
        for(int x:arr)
            System.out.print(x+" ");
    }
}



堆排序
算法描述：
堆排序：对简单选择排序的优化,将序列构建成大顶堆,将根节点与最后一个节点交换，然后断开最后一个节点,重复第一、二步，直到所有节点断开。


图片演示：  


heapSort.gif


代码实现：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * 堆排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 稳定性：不稳定
 * n较大时适用
 * @author Philstar
 */
package SortingMethod;

public class HeapSort {
    public static void main(String[] args) {
        HeapSort hs = new HeapSort();
        int[] tree = {38, 27, 43, 3, 9, 82, 10};
        int n = tree.length;
        hs.heapSort(tree,n);
        hs.printArr(tree);
    }
    // 堆排序
    void heapSort(int[] tree, int n) {
        buildHeap(tree, n);
        for (int i = n - 1; i >= 0; i--) {
            swap(tree, i, 0);
            heaping(tree, i, 0);
        }
    }
    // 将数组 tree 创建为大小为 n 的堆
    void buildHeap(int[] tree, int n) {
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heaping(tree, n, i);
        }
    }
    // 堆积以节点 i 为根的子树，n 为堆的大小
    void heaping(int[] tree, int n, int i) {
        if (i >= n) {
            return;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && tree[c1] > tree[max])
            max = c1;
        if (c2 < n && tree[c2] > tree[max])
            max = c2;
        if (max != i) {
            swap(tree, max, i);
            heaping(tree, n, max);
        }
    }
    // 交换 tree[] 的 max 和 i 索引下的值
    void swap(int[] tree, int max, int i) {
        int temp = tree[max];
        tree[max] = tree[i];
        tree[i] = temp;
    }
    // 打印数组
    void printArr(int[] arr) {
        for (int x : arr)
            System.out.print(x + " ");
    }
}

    


    
    
    
	  
---------------- The End ----------------

    
        
      
	  
	  

	  

	   本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布

	    
	    本文地址：https://philxin.top/2019/09/22/Java排序算法总结/
转载请注明出处，谢谢！
	    
	  

	  


      
    
  

  
  
  
  


  



          

          
    
    

  

        

          
  
  

    

      
      
      
    

  


  
  


      

    


    

    
  

    
    0%