盘点常用Java排序算法

本文主要介绍Java的七种常见排序算法的实现,对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆排序进行原理分析与实例介绍,下面一起来看一下吧:

本文主要介绍Java的七种常见排序算法的实现,对选择排序、插入排序、冒泡排序、归并排序、快速排序、希尔排序、最小堆排序进行原理分析与实例介绍,下面一起来看一下吧:

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243
这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

一、选择排序(SelectSort)

一、选择排序(SelectSort)

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

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

public class SelectSort {

public class SelectSort {

public static void selectSort(int[] array) {

public static void selectSort(int[] array) {

int i;

int i;

int j;

int j;

int temp;

int temp;

int flag;

int flag;

for (i = 0; i < array.length; i++) {

for (i = 0; i < array.length; i++) {

temp = array[i];

temp = array[i];

flag = i;

flag = i;

for (j = i + 1; j < array.length; j++) {

for (j = i + 1; j < array.length; j++) {

if (array[j] < temp) {

if (array[j] < temp) {

temp = array[j];

temp = array[j];

flag = j;

flag = j;

}

}

}

}

if (flag != i) {

if (flag != i) {

array[flag] = array[i];

array[flag] = array[i];

array[i] = temp;

array[i] = temp;

}

}

}

}

}

}

public static void main(String[] args) {

public static void main(String[] args) {

int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };

int[] a = { 5, 1, 9, 6, 7, 2, 8, 4, 3 };

selectSort;

selectSort;

for (int i = 0; i < a.length; i++) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i] + ” “);

System.out.print(a[i] + ” “);

}

}

}

}

}

}

二、插入排序(InsertSort)

二、插入排序(InsertSort)

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

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

public class InsertSort {

public class InsertSort {

public static void insertSort {

public static void insertSort {

if (a != null) {

if (a != null) {

for (int i = 1; i < a.length; i++) {

for (int i = 1; i < a.length; i++) {

int temp = a[i];

int temp = a[i];

int j = i;

int j = i;

if (a[j – 1] > temp) {

if (a[j – 1] > temp) {

while (j >= 1 && a[j – 1] > temp) {

while (j >= 1 && a[j – 1] > temp) {

a[j] = a[j – 1];

a[j] = a[j – 1];

j–;

j–;

}

}

}

}

a[j] = temp;

a[j] = temp;

}

}

}

}

}

}

int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };

int[] a = { 5, 1, 7, 2, 8, 4, 3, 9, 6 };

// int[] a =null;

// int[] a =null;

insertSort;

insertSort;

}

}

}

}

}

}

三、冒泡排序(BubbleSort)

三、冒泡排序(BubbleSort)

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

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

public class BubbleSort {

public class BubbleSort {

public static void bubbleSort(int array[]) {

public static void bubbleSort(int array[]) {

int temp = 0;

int temp = 0;

int n = array.length;

int n = array.length;

for (int i = n – 1; i >= 0; i–) {

for (int i = n – 1; i >= 0; i–) {

for (int j = 0; j < i; j++) {

for (int j = 0; j < i; j++) {

if (array[j] > array[j + 1]) {

if (array[j] > array[j + 1]) {

array[j] = array[j + 1];

array[j] = array[j + 1];

array[j + 1] = temp;

array[j + 1] = temp;

}

}

}

}

}

}

}

}

int a[] = { 45, 1, 21, 17, 69, 99, 32 };

int a[] = { 45, 1, 21, 17, 69, 99, 32 };

bubbleSort;

bubbleSort;

}

}

}

}

}

}

四、归并排序(MergeSort)

四、归并排序(MergeSort)

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

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

public class MergeSort {

public class MergeSort {

public static void merge(int array[], int p, int q, int r) {

public static void merge(int array[], int p, int q, int r) {

int i, j, k, n1, n2;

int i, j, k, n1, n2;

n1 = q – p + 1;

n1 = q – p + 1;

n2 = r – q;

n2 = r – q;

int[] L = new int[n1];

int[] L = new int[n1];

int[] R = new int[n2];

int[] R = new int[n2];

for (i = 0, k = p; i < n1; i++, k++)

for (i = 0, k = p; i < n1; i++, k++)

L[i] = array[k];

L[i] = array[k];

for (i = 0, k = q + 1; i < n2; i++, k++)

for (i = 0, k = q + 1; i < n2; i++, k++)

R[i] = array[k];

R[i] = array[k];

for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {

for (k = p, i = 0, j = 0; i < n1 && j < n2; k++) {

if (L[i] > R[j]) {

if (L[i] > R[j]) {

array[k] = L[i];

array[k] = L[i];

i++;

i++;

} else {

} else {

array[k] = R[j];

array[k] = R[j];

j++;

j++;

}

}

}

}

if (i < n1) {

if (i < n1) {

for (j = i; j < n1; j++, k++)

for (j = i; j < n1; j++, k++)

array[k] = L[j];

array[k] = L[j];

}

}

if (j < n2) {

if (j < n2) {

for (i = j; i < n2; i++, k++) {

for (i = j; i < n2; i++, k++) {

array[k] = R[i];

array[k] = R[i];

}

}

}

}

}

}

public static void mergeSort(int array[], int p, int r) {

public static void mergeSort(int array[], int p, int r) {

if {

发表评论

电子邮件地址不会被公开。 必填项已用*标注