java选择排序简书_Java排序算法

柔情只为你懂 2022-10-22 13:53 32阅读 0赞

(1)快速排序

在一个待排序的序列中，设置两个标记位，一个代表开始位(start)(从0开始)，一个代表结束位(end)(数组的长度-1)。再设置两个变量，分别代表低位的数(low)和高位的数(high)，然后选定一个标准数(standard)初始时standard = array\[start\]，以这个数为标准，从结束位开始往左查找(low和high比喻成指针)，如果array\[high\]比标准数大，则继续往左移动即high--，如果比标准数小，则用右边指针对应的数替换左边指针对应位置的数，替换后左边指针开始与标准数比较，如果array\[low\]比标准数小，则向右移动，即low++，如果比标准数大，则用左边指针对应的数替换右边指针对应位置的数，替换右边指针开始活跃，如此循环，直到两个指针重合，此时，把标准数放到两个指针重合的位置，这样就把比标准数小的数放到了标准数左边，比标准数大的数就放到了标准数右边。然后，把标准数赋值给low或者high，此时左边的序列的开始位为start，结束位为low或者high，右边的序列的开始位为high + 1，结束位为end。以此重复上述的步骤形成递归。

图解

![4ce53b113126][]

快速排序

代码

package sort;

import java.util.Arrays;

public class QuickSort \{

public static void main(String\[\] args) \{

int\[\] arr = \{12,3,43,7,5,56,4,5,9\};

quickSort(arr, 0, arr.length - 1);

System.out.println("排序结果为：" + Arrays.toString(arr));

public static void quickSort(int\[\] arr,int start,int end) \{

if (start < end) \{//循环条件

//把序列中第0个数字作为标准数

int standard = arr\[start\];

//记录需要排序的下标

int low = start;

int high = end;

//循环找出比标准数大的数和比标准数小的数

while(low < high) \{

//右边的数字比标准数大

while(low < high && arr\[high\] >= standard) \{

high--;

//当右边的数比标准数小，用右边的数替换左边的数

arr\[low\] = arr\[high\];

//如果左边的数字比标准数小

while (low < high && arr\[low\] <= standard) \{

low++;

//当左边的数字比标准数大，用左边的数字替换右边的数字

arr\[high\] = arr\[low\];

//当low和high重合时，把标准数赋值给low或者high

arr\[low\] = standard;

//此时序列分两部分，左边为小的数，右边为大的数。

//处理所有小的数字

quickSort(arr, start, low);

//处理所有大的数字

quickSort(arr, low + 1, end);

(2)冒泡排序

序列中的元素两两排序，选出大的元素放到后面即与小的元素交换位置，在剩下的序列中再两两排序，重复这个步骤。两层for循环控制，外层控制轮数，轮数为数组长度-1，内层循环控制比较次数，比较次数为数组长度-轮数，如果i从0开始，还要减1，即是数组长度-轮数-1，如果i从1开始，就数组长度-轮数。

图解

![4ce53b113126][]

冒泡排序

代码

package sort;

import java.util.Arrays;

public class BubbleSort \{

public void bubbleSort(int\[\] arr) \{

int length = arr.length;

int temp;

for(int i=0; i

for(int j=0; j

if (arr\[j\]>arr\[j+1\]) \{

temp = arr\[j\];

arr\[j\] = arr\[j+1\];

arr\[j+1\] = temp;

public static void main(String\[\] args) \{

int\[\] a = \{63,35,3,9,39,43,0,24,1\};

BubbleSort bSort = new BubbleSort();

bSort.bubbleSort(a);

System.out.println("排序结果为：" + Arrays.toString(a));

(3)直接插入排序

从已经排好序的序列中插入数字，在一个待排序的序列中，默认第一个数字就是一个排好序的序列，然后遍历除了第一个数字的之外的数字，所以for循环中的i = 1，要插入的数为insertNum = i，已经排好序的序列从j = i - 1这个位置开始遍历比较，序列从后到前循环，将大于insertNum的数向后移动一格。当insertNum大于与之相比的数时，insertNum插入到与之比较的数前面。

图解

![4ce53b113126][]

插入排序

代码

package sort;

import java.util.Arrays;

public class InsertSort \{

public static void main(String\[\] args) \{

int\[\] arr = \{2,32,3,5,4,1,9,12\};

insertSort(arr);

System.out.println("排序结果为：" + Arrays.toString(arr));

public static void insertSort(int\[\] arr) \{

//遍历所有数字，第一个除外

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

int insertNum = arr\[i\];//要插入的数字

int j = i-1;//已经排好序的序列长度

//序列从后到前循环，将大于insertNum的数向后移动一格

while (j>=0 && insertNum < arr\[j\]) \{

arr\[j+1\] = arr\[j\];//元素向后移动一位

j--;//往回遍历

//当insertNum大于与之相比的数时，insertNum插入到与之比较的数前面即arr\[j+1\]

arr\[j+1\] = insertNum;

(4)简单选择排序

遍历整个序列选出最小的数放在最前面，然后遍历剩下的序列，将最小的数放在最前面，重复这个步骤。记住当前位置的数字和位置，初始时默认记住第一个数，然后遍历当前位置之后的序列，选出比当前位置小的数，并记住其值和位置，然后和之前记住的数交换位置。

图解

![4ce53b113126][]

简单选择排序

代码

package sort;

import java.util.Arrays;

public class SelectSort \{

public static void main(String\[\] args) \{

int\[\] a = \{25,3,9,6,1,0,12,8\};

selectSort(a);

System.out.println("排序结果为：" + Arrays.toString(a));

public static void selectSort(int\[\] a) \{

//遍历所有数字

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

int key = a\[i\];//记住当前的数字

int position = i;//记住当前位置

//遍历当前位置后面所有的数字，并与当前数字进行比较

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

if (key > a\[j\]) \{

key = a\[j\];//小的数赋值给key

position = j;//记住小数的位置

//与小的数交换位置

a\[position\] = a\[i\];

a\[i\] = key;

(5)希尔排序

希尔排序也属于插入排序，相比于直接插入排序，排序速度更快，用于处理数据量大时。

步骤：

1、设数组的元素个数为n，用n/2得到一个数k，k作为步数或者叫增量。从第一个数开始将下标差值为k的数分为一组，然后把分好组的序列进行插入排序使它们构成有序序列。

2、排完一轮后，再将上一轮得到的k/2，从第一个数开始将下标差值为k的数分为一组，然后把分好组的序列进行插入排序使它们构成有序序列。

3、重复第二个步骤直到k=0。

图解

![4ce53b113126][]

希尔排序

代码

package sort;

import java.util.Arrays;

public class ShellSort \{

public static void main(String\[\] args) \{

int\[\] a = \{2,1,5,7,8,9,0\};

shellSort(a);

System.out.println("排序结果为：" + Arrays.toString(a));

public static void shellSort(int\[\] a) \{

//遍历所有的步长

for (int d = a.length/2; d > 0; d/=2) \{

//根据步长遍历所有的元素

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

//遍历本组的所有元素

for (int j = i - d; j >= 0; j-=d) \{

//如果当前元素大于加上步长后的那个元素

if (a\[j\] > a\[j+d\]) \{

int temp = a\[j\];

a\[j\] = a\[j+d\];

a\[j+d\] = temp;

[4ce53b113126]: /images/20221022/05abfde7d13e46198f6f490b4ae121d5.png

java选择排序简书_Java排序算法

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Java算法：选择排序

相关 Java 与排序算法（2）：选择排序

相关 java排序算法之选择排序

相关 Java经典算法冒泡排序&&选择排序

相关 Java基本排序算法 -- 直接选择排序

相关 java选择排序简书_Java排序算法

相关【JAVA】算法排序（一）——选择排序法

相关 Java-排序算法之选择排序算法

相关 Java实现排序算法（一）——选择排序

相关 java排序算法：冒泡排序、插入排序、选择排序、快速排序