常见的七种Java排序算法原理是什么，怎样实现？
这篇文章给大家分享的是Java排序算法的相关内容，下文介绍了七种常见的排序及其原理和实现。小编觉得挺实用的，因此分享给大家做个参考，文中示例代码介绍的很详细，感兴趣的朋友接下来一起跟随小编看看吧。
一、选择排序(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[i];
flag = i;
for (j = i + 1;
j array.length;
j++) {
if (array[j] temp) {
temp = array[j];
flag = j;
}
}
if (flag != i) {
array[flag] = array[i];
array[i] = 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[i] + " ");
}
}
}
二、插入排序(InsertSort)
基本原理：对于给定的一组数据，初始时假设第一个记录自成一个有序序列，其余记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
public class InsertSort {
public static void insertSort(int[] a) {
if (a != null) {
for (int i = 1;
i a.length;
i++) {
int temp = a[i];
int j = i;
if (a[j - 1] >
temp) {
while (j >
= 1 &
&
a[j - 1] >
temp) {
a[j] = a[j - 1];
j--;
}
}
a[j] = 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[i] + " ");
}
}
}
三、冒泡排序(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[j] >
array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 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[i] + " ");
}
}
}
四、归并排序(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 int[n1];
int[] R = new int[n2];
for (i = 0, k = p;
i n1;
i++, k++)
L[i] = array[k];
for (i = 0, k = q + 1;
i n2;
i++, k++)
R[i] = array[k];
for (k = p, i = 0, j = 0;
i n1 &
&
j n2;
k++) {
if (L[i] >
R[j]) {
array[k] = L[i];
i++;
}
else {
array[k] = R[j];
j++;
}
}
if (i n1) {
for (j = i;
j n1;
j++, k++)
array[k] = L[j];
}
if (j n2) {
for (i = j;
i n2;
i++, k++) {
array[k] = R[i];
}
}
}
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[j] + " ");
}
}
}
五、快速排序(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[i];
while (i j) {
while (i j &
&
index = array[j])
j--;
if (i j)
array[i++] = array[j];
while (i j &
&
index >
array[i])
i++;
if (i j)
array[j--] = array[i];
}
array[i] = 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[i] + " ");
}
}
}
六、希尔排序(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[i];
for (j = i - h;
j >
= 0;
j -= h) {
if (temp a[j]) {
a[j + h] = a[j];
}
else
break;
}
a[j + 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[j] + " ");
}
}
}
七、最小堆排序(MinHeapSort)
基本原理：对于给定的n个记录，初始时把这些记录看作一颗顺序存储的二叉树，然后将其调整为一个小顶堆，然后将堆的最后一个元素与堆顶元素进行交换后，堆的最后一个元素即为最小记录；接着讲前(n-1)个元素重新调整为一个小顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次小的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最大记录，此时可得到一个有序序列。
public class MinHeapSort {
public static void adjustMinHeap(int[] a, int pos, int len) {
int temp;
int child;
for (temp = a[pos];
2 * pos + 1 = len;
pos = child) {
child = 2 * pos + 1;
if (child len &
&
a[child] >
a[child + 1])
child++;
if (a[child] temp)
a[pos] = a[child];
else
break;
}
a[pos] = 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 = array[0];
array[0] = array[i];
array[i] = 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[i] + " ");
}
}
}
关于Java排序算法的内容就分享到这里了，上述示例对帮助大家学习和理解这些排序算法有一定的帮助，需要的朋友可以参考，希望大家阅读完这篇文章能有所收获。最后，想要了解更多Java排序算法的内容，大家可以关注网络其它相关文章。
文本转载自PHP中文网
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 常见的七种Java排序算法原理是什么，怎样实现？
本文地址： https://pptw.com/jishu/655280.html