常用排序算法总结

 概述

在计算器科学与数学中,一个排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定排序方式进行排列的一种算法。本文将总结几类常用的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序,分别使用Java代码实现,简要使用图例方式介绍其实现原理。

算法原理及实现

1、冒泡排序

  • 原理图

常用排序算法总结

  • 理解

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

  • 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.     } 

2、选择排序

  • 原理图

常用排序算法总结

  • 理解

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

  • 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.     } 

冒泡排序和选择排序的区别

1、冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值;

2、冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置;

3、冒泡排序是通过数去找位置,选择排序是给定位置去找数。

3、插入排序

  • 原理图

常用排序算法总结

  • 理解

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

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

4、快速排序

  • 原理图

常用排序算法总结

  • 理解

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

  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 (i <= 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 (i <= 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 (i < 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.     } 

5、归并排序

  • 原理图

常用排序算法总结

  • 理解

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

  • Java Code

相关推荐