算法--排序--插入排序&&选择排序--JAVA

本文链接：https://blog.csdn.net/kai123wen/article/details/98191106

本文详细介绍了两种基本的排序算法——插入排序和选择排序。插入排序通过将每个元素插入到已排序序列的正确位置来实现排序，而选择排序则是通过在未排序部分找到最小（或最大）元素并将其放到已排序序列的末尾来完成排序过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

排序的分类（内部排序）：插入排序、选择排序、交换排序、归并排序、基数排序

这一篇先介绍前两种简单的 插入排序、 选择排序

插入排序：

当插入第 i 个元素时，之前的元素 array[0] array[1] … array[i-2] 均已经排序完毕，只需要将array[i] 与 array[0] array[1] … array[i-2] 中元素比较，找到第一个大于array[i] 的位置，然后将其插入。

看一个例子：

[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘
[5, 6]   3   1   8   7   2   4
↑        │
└────────┘
[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘
[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘
[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘
[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘
[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘
 
[1, 2, 3, 4, 5, 6, 7, 8]

看代码：

public class SortInsert {
	/*
	 * 插入排序
	 */
	public void insertSort(int array[]) {
		int boundaryEnd = 0;
		int boundaryStart = 0;
		for (int i = 1; i < array.length; i++) {
			for (int j = 0; j < i; j++) {
				if (array[i] < array[j]) {
					boundaryStart = j;
					boundaryEnd = i;
					insertNewArray(array, boundaryStart, boundaryEnd, array[i]);
				}
			}
		}
	}

	/*
	 * 这个函数的作用是：
	 * 将boundaryStart 与 boundaryEnd -1 之间元素后移一个单位
	 * 然后将目标数字插入到 boundaryStart 位置
	 * 如 2 3 4 1 -> 1 2 3 4
	 */
	public void insertNewArray(int array[], int boundaryStart, int boundaryEnd, int insertNum) {

		for (int j = boundaryEnd - 1; j >= boundaryStart; j--) {
			array[j + 1] = array[j];
		}
		array[boundaryStart] = insertNum;
	}
}

插入排序最重要的两点：

在元素选择好插入位置后，要将位置之后的有序区元素后移
如何实现在一个数组中就可以将元素后移？答：将要移动的元素存放在一个临时变量中，然后再将前面的元素依次后移，最后将临时变量中的值放进数组（我用语言说不太明白，还是看代码更好理解）

其余的就很简单了！

选择排序：

选择排序一种十分简单的排序算法，排序过程为：在未排序的序列中找到最小（大）的元素，然后将其与起始位置的元素交换，然后再从未排序的序列中选择最小（大）的元素，然后放在序列开头已经有序的序列结尾，依次进行此过程…

看一个例子：

交换前：

                           min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交换后：

	
0   5   2   6   9   3   1   4   8   7

继续交换前：

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交换后：

	
0   1   2   6   9   3   5   4   8   7

依次进行以上步骤

看代码：

public class SortSelect {
	/*
	 * 选择排序
	 */
	public void selectSort(int array[]) {

		int minNumIndex = 0;
		int temp = 0;
		for (int i = 0; i < array.length - 1; i++) {
			minNumIndex = findMinNumIndex(array, i);
			temp = array[i];
			array[i] = array[minNumIndex];
			array[minNumIndex] = temp;
		}
	}

	/*
	 *  获取到未排序序列中最小值的索引
	 */
	public int findMinNumIndex(int array[], int boundaryStart) {
		int minNumIndex = boundaryStart;
		int minNum = array[boundaryStart];
		for (int i = boundaryStart; i < array.length; i++) {
			if (array[i] < minNum) {
				minNumIndex = i;
				minNum = array[i];
			}
		}
		return minNumIndex;
	}
}