经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
常用排序算法及Java实现
来源:cnblogs  作者:taro_秋刀鱼  时间:2018/10/19 9:24:08  对本文有异议

概述

在计算器科学与数学中,一个排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定排序方式进行排列的一种算法。本文将总结几类常用的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。


算法原理及实现

1、冒泡排序
  • 原理图

image

  • 理解

通过重复地遍历要排序的列表,比较每对相邻的项目,并在顺序错误的情况下交换它们。

  • Java Code

  1. public class BubbleSort {
  2.   
  3.     // logic to sort the elements
  4.     public static void bubble_srt(int array[]) {
  5.         int n = array.length;
  6.         int k;
  7.         for (int m = n; m >= 0; m--) {
  8.             for (int i = 0; i < n - 1; i++) {
  9.                 k = i + 1;
  10.                 if (array[i] > array[k]) {
  11.                     swapNumbers(i, k, array);
  12.                 }
  13.             }
  14.             printNumbers(array);
  15.         }
  16.     }
  17.   
  18.     private static void swapNumbers(int i, int j, int[] array) {
  19.   
  20.         int temp;
  21.         temp = array[i];
  22.         array[i] = array[j];
  23.         array[j] = temp;
  24.     }
  25.   
  26.     private static void printNumbers(int[] input) {
  27.           
  28.         for (int i = 0; i < input.length; i++) {
  29.             System.out.print(input[i] + ", ");
  30.         }
  31.         System.out.println("\n");
  32.     }
  33.   
  34.     public static void main(String[] args) {
  35.         int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
  36.         bubble_srt(input);
  37.     }
  38. }

2、选择排序
  • 原理图

image

  • 理解

内部循环查找下一个最小(或最大)值,外部循环将该值放入其适当的位置。

  • Java Code

  1. public class SelectionSort {
  2.  
  3.     public static int[] doSelectionSort(int[] arr){
  4.          
  5.         for (int i = 0; i < arr.length - 1; i++)
  6.         {
  7.             int index = i;
  8.             for (int j = i + 1; j < arr.length; j++)
  9.                 if (arr[j] < arr[index]) 
  10.                     index = j;
  11.       
  12.             int smallerNumber = arr[index];  
  13.             arr[index] = arr[i];
  14.             arr[i] = smallerNumber;
  15.         }
  16.         return arr;
  17.     }
  18.      
  19.     public static void main(String a[]){
  20.          
  21.         int[] arr1 = {10,34,2,56,7,67,88,42};
  22.         int[] arr2 = doSelectionSort(arr1);
  23.         for(int i:arr2){
  24.             System.out.print(i);
  25.             System.out.print(", ");
  26.         }
  27.     }
  28. }

3、插入排序
  • 原理图

image

  • 理解

每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。

  • Java Code

  1. public class InsertionSort {
  2.  
  3.     public static void main(String a[]){
  4.         int[] arr1 = {10,34,2,56,7,67,88,42};
  5.         int[] arr2 = doInsertionSort(arr1);
  6.         for(int i:arr2){
  7.             System.out.print(i);
  8.             System.out.print(", ");
  9.         }
  10.     }
  11.      
  12.     public static int[] doInsertionSort(int[] input){
  13.          
  14.         int temp;
  15.         for (int i = 1; i < input.length; i++) {
  16.             for(int j = i ; j > 0 ; j--){
  17.                 if(input[j] < input[j-1]){
  18.                     temp = input[j];
  19.                     input[j] = input[j-1];
  20.                     input[j-1] = temp;
  21.                 }
  22.             }
  23.         }
  24.         return input;
  25.     }
  26. }

4、快速排序
  • 原理图

image

  • 理解

将原问题分解为若干个规模更小,但结构与原问题相似的子问题,递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

  • Java Code

  1. public class QuickSort {
  2.      
  3.     private int array[];
  4.     private int length;
  5.  
  6.     public void sort(int[] inputArr) {
  7.          
  8.         if (inputArr == null || inputArr.length == 0) {
  9.             return;
  10.         }
  11.         this.array = inputArr;
  12.         length = inputArr.length;
  13.         quickSort(0, length - 1);
  14.     }
  15.  
  16.     private void quickSort(int lowerIndex, int higherIndex) {
  17.          
  18.         int i = lowerIndex;
  19.         int j = higherIndex;
  20.         // calculate pivot number, I am taking pivot as middle index number
  21.         int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
  22.         // Divide into two arrays
  23.         while (<= j) {
  24.             /**
  25.              * In each iteration, we will identify a number from left side which 
  26.              * is greater then the pivot value, and also we will identify a number 
  27.              * from right side which is less then the pivot value. Once the search 
  28.              * is done, then we exchange both numbers.
  29.              */
  30.             while (array[i] < pivot) {
  31.                 i++;
  32.             }
  33.             while (array[j] > pivot) {
  34.                 j--;
  35.             }
  36.             if (<= j) {
  37.                 exchangeNumbers(i, j);
  38.                 //move index to next position on both sides
  39.                 i++;
  40.                 j--;
  41.             }
  42.         }
  43.         // call quickSort() method recursively
  44.         if (lowerIndex < j)
  45.             quickSort(lowerIndex, j);
  46.         if (< higherIndex)
  47.             quickSort(i, higherIndex);
  48.     }
  49.  
  50.     private void exchangeNumbers(int i, int j) {
  51.         int temp = array[i];
  52.         array[i] = array[j];
  53.         array[j] = temp;
  54.     }
  55.      
  56.     public static void main(String a[]){
  57.          
  58.         MyQuickSort sorter = new MyQuickSort();
  59.         int[] input = {24,2,45,20,56,75,2,56,99,53,12};
  60.         sorter.sort(input);
  61.         for(int i:input){
  62.             System.out.print(i);
  63.             System.out.print(" ");
  64.         }
  65.     }
  66. }

5、归并排序
  • 原理图

image

  • 理解

将待排序的数列分成若干个长度为1的子数列,然后将这些数列两两合并;得到若干个长度为2的有序数列,再将这些数列两两合并;得到若干个长度为4的有序数列,再将它们两两合并;直接合并成一个数列为止。

  • Java Code

  1. public class MergeSort {
  2.      
  3.     private int[] array;
  4.     private int[] tempMergArr;
  5.     private int length;
  6.  
  7.     public static void main(String a[]){
  8.          
  9.         int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
  10.         MyMergeSort mms = new MyMergeSort();
  11.         mms.sort(inputArr);
  12.         for(int i:inputArr){
  13.             System.out.print(i);
  14.             System.out.print(" ");
  15.         }
  16.     }
  17.      
  18.     public void sort(int inputArr[]) {
  19.         this.array = inputArr;
  20.         this.length = inputArr.length;
  21.         this.tempMergArr = new int[length];
  22.         doMergeSort(0, length - 1);
  23.     }
  24.  
  25.     private void doMergeSort(int lowerIndex, int higherIndex) {
  26.          
  27.         if (lowerIndex < higherIndex) {
  28.             int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
  29.             // Below step sorts the left side of the array
  30.             doMergeSort(lowerIndex, middle);
  31.             // Below step sorts the right side of the array
  32.             doMergeSort(middle + 1, higherIndex);
  33.             // Now merge both sides
  34.             mergeParts(lowerIndex, middle, higherIndex);
  35.         }
  36.     }
  37.  
  38.     private void mergeParts(int lowerIndex, int middle, int higherIndex) {
  39.  
  40.         for (int i = lowerIndex; i <= higherIndex; i++) {
  41.             tempMergArr[i] = array[i];
  42.         }
  43.         int i = lowerIndex;
  44.         int j = middle + 1;
  45.         int k = lowerIndex;
  46.         while (<= middle && j <= higherIndex) {
  47.             if (tempMergArr[i] <= tempMergArr[j]) {
  48.                 array[k] = tempMergArr[i];
  49.                 i++;
  50.             } else {
  51.                 array[k] = tempMergArr[j];
  52.                 j++;
  53.             }
  54.             k++;
  55.         }
  56.         while (<= middle) {
  57.             array[k] = tempMergArr[i];
  58.             k++;
  59.             i++;
  60.         }
  61.     }
  62. }

参考链接

Java Sorting Algorithms

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号