（代码+注释+动图+java）排序算法：冒泡，选择，插入，快排，归并，希尔
程序员文章站
2022-06-04 15:00:01
...
排序算法：冒泡，选择，插入，快排，归并，希尔
目录
冒泡排序
外层循环总共比较数组长度次，内循环都是进行从头到尾（a.length-1-i ）两两比较，将大数往后挪移（冒泡）。
外层一次循环结束，就会将这时的最大数放入末尾
//（第1次是最大数放入数组倒数第一个位置）
//（第2次是除最大数外最大数放入数组倒数第2个位置）
//（第3次是除最大数次大数外 最大数 放入数组倒数第3个位置）......
package sort;
/**
*
* @author shen_i
* 冒泡排序
*/
public class A_BubbleSort {
void bubble(int[] a ) {
// 3,6,1,2,8,5,3
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length-1-i; j++) {
// j < a.length-1-i -i表示不将最后i个数加入比较
//-1是因为循环需要比较j和j+1，如果不减一，就会数组越界
//ps.冒泡比直接两层循环进行比较唯一更优化的地方就是内循环每次少比较i次
int temp ;//临时变量，用于变量置换
if ( a[j]>a[j+1] ) {
//如果后边元素更小(前变更大)
//进行位置互换
temp = a[j];
a[j]=a[j+1];
a[j+1] = temp;//error:要置换为临时变量temp，不是a[i]
}
}
//（第1次是最大数放入数组倒数第一个位置）
//（第2次是除最大数外最大数放入数组倒数第2个位置）
//（第3次是除最大数次大数外 最大数 放入数组倒数第3个位置）......
}
printArray(a);
}
/**
*
* 重写数组的遍历方法
* 打印数组
*/
void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
public static void main(String[] args) {
int[] a = {3,6,1,2,8,5,3};
new A_BubbleSort().bubble(a);
}
}
选择排序
依次比较每个数和其他数（数组下标比他大的数，即排在他后边的），每一个外层循环规定 i 位置数和其后续数进行比较，如果比其小，记下其下标，继续比较，还有更小的再进行替换，循环结束就找到了最小的数的下标，然后进行和i位置数交换。然后进行循环下一个数。
package sort;
/**
*
* @author shen_i
* 选择排序
*/
public class B_SelectionSort {
void Selection(int[] a) {
for (int i = 0; i < a.length; i++) {
int s_temp = i;//初始化为本次循环的比较者
int temp;
for (int j = i+1; j < a.length; j++) {
if (a[s_temp]>a[j]) { //error:这一块一定要比较 a[s_temp]与a[j]
s_temp = j;//将数组下标记下来，先不进行置换
}
}
if (s_temp!=i) {
//进行置换
temp = a[i];
a[i] = a[s_temp];
a[s_temp]=temp;
}
}
printArray(a);
}
/**
*
* 重写数组的遍历方法
* 打印数组
*/
void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
public static void main(String[] args) {
int[] a = {3,6,1,2,8,5,3};
new B_SelectionSort().Selection(a);
}
}
插入排序
假想起始排序好的数组只有a[i],外层循环依次一个个放入排序好的数组，然后将放入的数从排序好的数组末尾进行比较，如果新加入的数更小，就往前继续比较，直到比较到前一个数比他小，就结束此次循环；再次加入一个新数，进行循环。
package sort;
public class C_InsertionSort {
//3,6,1,2,8,5,3
void insertion(int[] a) {
for (int i = 1; i < a.length; i++) {//i表示最外层需要排序的一个数
int s_temp =i;//s_temp代表比较数坐标之一，最外层向内移动数的坐标
for (int j = i-1; j >= 0; j--) {//逐个向前进行比较
System.out.println(j);
if (a[s_temp]<a[j]) {
//i位置数更小，置换
int temp = a[s_temp];
a[s_temp]=a[j];
a[j]=temp;
s_temp--;//当最外层数小，往前移动后，s_temp代表移动后的坐标
//进而让它和他的前一个进行比较，看是否需要置换
//不需要置换执行else
}
else {
//已经比此时的a[j]大，肯定比前边的肯定更大
break;
}
}
System.out.println();
}
printArray(a);
}
/**
*
* 重写数组的遍历方法
* 打印数组
*/
void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
public static void main(String[] args) {
int[] a = {3,6,1,2,8,5,3};
new C_InsertionSort().insertion(a);
}
}
归并排序
分割数组，直到分割到只有一个数的数组序列，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
package sort;
import java.util.Arrays;
/**
*
* @author shen_i
* 归并排序
*/
public class E_MergeSort {
/*
* 进行数组分割
* 分割至left和right数组都只有一个数的时候进入merge方法
*
*/
public int[] cut(int[] a) {
//如果a长度=1，则返回
if (a.length<2) {
return a;
}
//复制数组，后边操作arr
int[] arr = Arrays.copyOf(a, a.length);//完全复制a数组，arr==a
int mid =(int) Math.floor(arr.length / 2);//floor方法是返回给定参数最大的整数，该整数小于或等给定的参数
//取中分割
//数组left为原来数组左半边
int[] left = Arrays.copyOfRange(arr, 0, mid);//copyOfRange是复制0~mid，含0不含mid
//数组right为原来数组右半边
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
//此时方法参数cut（left）,cut(right)是进行递归分割
//分割至left和right数组都只有一个数的时候进入merge方法
return merge(cut(left),cut(right));
}
/*
* 合并left 和 right数组 并进行left和right比较排序加入结果集，小的先加入
*/
int[] merge(int[] left,int[] right) {
int[] result = new int[left.length+right.length];//结果集，数组大小为left+right长度
int result_num = 0;//result的存储下标
//如果left和right都还有数存在
while(left.length > 0 && right.length > 0)
{
//如果左数<右数
if (left[0] < right[0] ) {
//将左数 加入结果集
//表示已经将小的数加入结果
result[result_num++] = left[0];
//左数组将第一个数删除即底下copy除第一个数的left数组）
left = Arrays.copyOfRange(left, 1, left.length);//开销大，可以优化
}
else {
//将右数 加入结果集
// 此时右数小，加入
result[result_num++] = right[0];
//right数组删除第一个数（即底下copy除第一个数的right数组）
right = Arrays.copyOfRange(right, 1, right.length);//开销大，可以优化
}
//继续进行左右比较，加入小数
}
//退出循环，表示现在只有left或者right其中 某 一个 数组 还没有排序完
//此时left或right只有一个里还有数存在
//此时如果left数组还有数，
//进入循环 将其全部加入结果集
if(left.length>0)
{
for (int i = 0; i < left.length; i++) {
result[result_num++]=left[i];
}
}
//此时如果right数组还有数，
//进入循环 将其全部加入结果集
if(right.length>0)
{
for (int i = 0; i < right.length; i++) {
result[result_num++]=right[i];
}
}
return result;
}
/*
* 简单的打印数组方法
*/
static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] a= {31,2,12,3,12,3,1,0,23,43,1};
printArray(a);
int[] result = new E_MergeSort().cut(a);
printArray(result);
}
}
------------------
难度直线上升，前边都是简单好理解的算法，后边两个难理解
-------------------
快速排序
从数列中挑出一个元素，称为 “基准”，然后遍历数组，比基准小的放在前边，比基准小的放在后边；然后将数组逻辑上分为两半：基准前和基准后，这两部分内再重新各自找基准，小的放前边，大的放后边；然后同理将各自数组再分割......直到最终分割为一个数。（其实算法代码不是完全那样编写的，因为那样需要众多额外空间，具体代码有详细注释）
package sort;
public class D_QuickSort {
void quickSort(int[] a,int begin,int end) {
//判断begin<end，直接返回
if (begin>end) {
return;
}
//1.确定基准,key
int key = a[begin];
int i = begin;
int j = end;
//2.搜索，在左边找出比key大的，右边找出比key小的
while(i!=j)//直到从左到右的搜索连接上，才退出
{
//一定是先进行从后往前搜索，原因在50行代码那块
while(a[j]>=key && i<j)//右边搜索，若右边大则逐个往左走
{
j--;
}
while(a[i]<=key&& i<j)//左边搜索，若左边小则逐个往右
{
i++;
}
//现在是已经找到 左边一个比key大，右边一个比key小
//他俩进行置换
if (i<j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//置换完成后，若全部数没遍历完，继续左右搜索，进行置换
}
//一遍搜索完毕，i=j
//a[begin]放置中间数
//将key放置到a[i]位置（中间位置，此时i=j，a[i]=a[j]）
a[begin] = a[i];
a[i] =key;
/*
*
* 此时有个问题，a[i]=a[j] 此时的中间数a[i]一定比key小吗？
*
* 一定比key小
* 开始分析：
* key=5,key是基准
* 0 1 2 3 4 5 数组下标，i，j都是下标
* a={5,5,4,6,6,4}
* 第一次找到的i=3 ;j=5，将a[i]和a[j]互换
* 0 1 2 3 4 5 数组下标，i，j都是下标
* a={5,5,4,4,6,6}
* 继续搜索，
* 重点来了，此时搜索是先从后往前搜索（后边的数都大于key）
* 所以j--,j=3 ，现在i==j
* so a[3]<key
* {如果是从前往后先搜索，结果 i++,i=5=j,此时a[i]=a[j]>key ，这样不行}
*
*
*/
//继续进行递归，根据中间数的位置i (此时i=j)，将数组分为两半
//将原来的数组分割开，运用原来一模一样方法进行分段处理（分段进行快排）
//左半边，begin~i-1
quickSort(a,begin, i-1);
//右半边，i+1~end
quickSort( a,i+1, end);
}
/**
*
* 重写数组的遍历方法
* 打印数组
*/
static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int a[] = {24,4234,53421,632,73,7,4,231,643,32};
printArray(a);
new D_QuickSort().quickSort(a,0,a.length-1);
printArray(a);
}
}
希尔排序
将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
- 逻辑上将数组分割分组（此时分割间隔是最大的时候，后边会逐步缩小分割间隔）
2.依次将每组进行内部排序交换
3.缩小分割间隔，比如原来是隔4个数为一组，现在就是隔2个为一组，继续排序（此时插入更轻松）
......一直分割到排序结束
思想不难理解
package sort;
/**
*
* @author shen_i
* 希尔排序
*/
public class F_ShellSort {
void shellSort(int[] a) {
//第一层for是将数组分割，依次分割的越来越小
for (int gap = a.length/2; gap > 0; gap /= 2) {
//第2层依次遍历分割后的每一个逻辑组的一个数i，每一个i表示一个逻辑组
for (int i = gap; i < a.length; i++) {
int value = a[i];
int j;
//第3层遍历每一个逻辑组内的数，并排序
for ( j = i-gap; j>=0 && a[j]>value; j-=gap) {
//同一逻辑组内，后边比前边小
//互换
a[j+gap] = a[j];
}
a[j+gap]=value;
}
}
printArray(a);
}
static void printArray(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void main(String[] args) {
int[] a= {31,412,2,3,6,54,4,53,13,765,2323,22,3,0};
printArray(a);
new F_ShellSort().shellSort(a);
}
}
上一篇： 夏季易怒烦躁快养脾
下一篇： Lua 学习笔记table篇（1）