（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。以此重复上述的步骤形成递归。
图解
快速排序
代码
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开始，就数组长度-轮数。
图解
冒泡排序
代码
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<length; i++) {
for(int j=0; j<length-i-1; 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插入到与之比较的数前面。
图解
插入排序
代码
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）简单选择排序
遍历整个序列选出最小的数放在最前面，然后遍历剩下的序列，将最小的数放在最前面，重复这个步骤。记住当前位置的数字和位置，初始时默认记住第一个数，然后遍历当前位置之后的序列，选出比当前位置小的数，并记住其值和位置，然后和之前记住的数交换位置。
图解
简单选择排序
代码
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。
图解
希尔排序
代码
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;
}
}
}
}
}
}
网友评论