常用Java排序算法详解

来源：本站原创|时间：2020-01-10|栏目：Java编程|点击：163 次

一、选择排序(SelectSort)

基本原理：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个为止。

public class SelectSort 
 public static void selectSort(int array) 
 int i;
 int j;
 int temp;
 int flag;
 for (i = 0; i < array.length; i++) 
 temp = array;
 flag = i;
 for (j = i + 1; j < array.length; j++) 
 if (array < temp) 
  temp = array;
  flag = j;
 
 
 if (flag != i) 
 array = array;
 array = temp;
 
 
 
 public static void main(String args) 
 int a =  5, 1, 9, 6, 7, 2, 8, 4, 3 ;
 selectSort(a);
 for (int i = 0; i < a.length; i++) 
 System.out.print(a + " ");

二、插入排序(InsertSort)

基本原理：对于给定的一组数据，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。

public class InsertSort 
 public static void insertSort(int a) 
 if (a != null) 
 for (int i = 1; i < a.length; i++) 
 int temp = a;
 int j = i;
 if (aj - 1 > temp) 
  while (j >= 1 && aj - 1 > temp) 
  a = aj - 1;
  j--;
  
 
 a = temp;
 
 
 
 public static void main(String args) 
 int a =  5, 1, 7, 2, 8, 4, 3, 9, 6 ;
 // int a =null;
 insertSort(a);
 for (int i = 0; i < a.length; i++) 
 System.out.print(a + " ");

三、冒泡排序(BubbleSort)

基本原理：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前(n-1)个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个为止。

public class BubbleSort 
 public static void bubbleSort(int array) 
 int temp = 0;
 int n = array.length;
 for (int i = n - 1; i >= 0; i--) 
 for (int j = 0; j < i; j++) 
 if (array > arrayj + 1) 
  temp = array;
  array = arrayj + 1;
  arrayj + 1 = temp;
 
 
 
 
 public static void main(String args) 
 int a =  45, 1, 21, 17, 69, 99, 32 ;
 bubbleSort(a);
 for (int i = 0; i < a.length; i++) 
 System.out.print(a + " ");

四、归并排序(MergeSort)

基本原理：利用递归与分治技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。对于给定的一组记录(假设共有n个记录)，首先将每两个相邻的长度为1的子序列进行归并，得到n/2(向上取整)个长度为2或1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列。

public class MergeSort 
 public static void merge(int array, int p, int q, int r) 
 int i, j, k, n1, n2;
 n1 = q - p + 1;
 n2 = r - q;
 int L = new intn1;
 int R = new intn2;
 for (i = 0, k = p; i < n1; i++, k++)
 L = array;
 for (i = 0, k = q + 1; i < n2; i++, k++)
 R = array;
 for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) 
 if (L > R) 
 array = L;
 i++;
  else 
 array = R;
 j++;
 
 
 if (i < n1) 
 for (j = i; j < n1; j++, k++)
 array = L;
 
 if (j < n2) 
 for (i = j; i < n2; i++, k++) 
 array = R;
 
 
 
 public static void mergeSort(int array, int p, int r) 
 if (p < r) 
 int q = (p + r) / 2;
 mergeSort(array, p, q);
 mergeSort(array, q + 1, r);
 merge(array, p, q, r);
 
 
 public static void main(String args) 
 int a =  5, 4, 9, 8, 7, 6, 0, 1, 3, 2 ;
 mergeSort(a, 0, a.length - 1);
 for (int j = 0; j < a.length; j++) 
 System.out.print(a + " ");

五、快速排序(QuickSort)

基本原理：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。

public class QuickSort 
 public static void sort(int array, int low, int high) 
 int i, j;
 int index;
 if (low >= high)
 return;
 i = low;
 j = high;
 index = array;
 while (i < j) 
 while (i < j && index <= array)
 j--;
 if (i < j)
 arrayi++ = array;
 while (i < j && index > array)
 i++;
 if (i < j)
 arrayj-- = array;
 
 array = index;
 sort(array, low, i - 1);
 sort(array, i + 1, high);
 
 public static void quickSort(int array) 
 sort(array, 0, array.length - 1);
 
 public static void main(String args) 
 int a =  5, 8, 4, 6, 7, 1, 3, 9, 2 ;
 quickSort(a);
 for (int i = 0; i < a.length; i++) 
 System.out.print(a + " ");

六、希尔排序(ShellSort)

基本原理：先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对减少，然后对各个子序列分别进行直接插入排序，待整个待排序序列"基本有序后"，最后再对所有元素进行一次直接插入排序。

public class ShellSort 
 public static void shellSort(int a) 
 int len = a.length;
 int i, j;
 int h;
 int temp;
 for (h = len / 2; h > 0; h = h / 2) 
 for (i = h; i < len; i++) 
 temp = a;
 for (j = i - h; j >= 0; j -= h) 
  if (temp < a) 
  aj + h = a;
   else
  break;
 
 aj + h = temp;
 
 
 
 public static void main(String args) 
 int a =  5, 4, 9, 8, 7, 6, 0, 1, 3, 2 ;
 shellSort(a);
 for (int j = 0; j < a.length; j++) 
 System.out.print(a + " ");

七、最小堆排序(MinHeapSort)

基本原理：对于给定的n个记录，初始时把这些记录看作一颗顺序存储的二叉树，然后将其调整为一个小顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最小记录；接着讲前(n-1)个元素重新调整为一个小顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最大记录，此时可得到一个有序序列。

public class MinHeapSort 
 public static void adjustMinHeap(int a, int pos, int len) 
 int temp;
 int child;
 for (temp = a; 2 * pos + 1 <= len; pos = child) 
 child = 2 * pos + 1;
 if (child < len && a > achild + 1)
 child++;
 if (a < temp)
 a = a;
 else
 break;
 
 a = temp;
 
 public static void myMinHeapSort(int array) 
 int i;
 int len = array.length;
 for (i = len / 2 - 1; i >= 0; i--) 
 adjustMinHeap(array, i, len - 1);
 
 for (i = len - 1; i >= 0; i--) 
 int tmp = array0;
 array0 = array;
 array = tmp;
 adjustMinHeap(array, 0, i - 1);
 
 
 public static void main(String args) 
 int a =  5, 4, 9, 8, 7, 6, 0, 1, 3, 2 ;
 myMinHeapSort(a);
 for (int i = 0; i < a.length; i++) 
 System.out.print(a + " ");

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我们！

上一篇：探讨:如何在NDK中呼叫Java的class

栏目：Java编程

下一篇：java编程调用存储过程中得到新增记录id号的实现方法

本文标题：常用Java排序算法详解

本文地址：https://www.xiuzhanwang.com/a1/Javabiancheng/8495.html

更多Java编程

Java编程

常用Java排序算法详解

您可能感兴趣的文章

阅读排行

本栏相关

随机阅读