七大常见排序算法
- 直接插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 归并排序
下文后三种排序算法(后三种排序算法详解)
直接插入排序
算法描述：
- 定义两个下标（i 和 j）.i 从第二个元素开始，j 从 i 前面开始，进行循环，
- 途中定义一个 temp ，每次循环将 i 下标的元素放到 temp 中，与 j 进行比较转换(当 j 下标的元素大于 temp 中的元素，就将 j 位置的元素赋值给后一个元素，即i下标元素，j-- 继续与 temp 比较)
- 当 j-- 到小于 temp 中的元素时，一次循环就完成了，此后 i++ 继续重复如上循环.
描述虽复杂，烦请与算法实现步骤图结合思考.
代码实现：
public class InsertSort {
public void iSort(int[] array) {
for (int i = 1; i < array.length; i++) { // 从第二个元素开始（因为当数组只有一个元素时是有序的）
int temp = array[i]; // 设置一个 temp（为 i 下标的值） ,方便后续交换
int j = i-1; // 设置一个 j，让 j 为 i 的前一个，在循环的过程中与 temp 中的元素进行交换
for (; j >= 0; j--) { // j 与 temp 每次比较完向前移动，继续和前一个元素进行对比
if (array[j] > temp){ // 即前一个元素(j)大于后一个元素(j+1/temp)，进行交换，j --
array[j+1] = array[j]; // 将前一个元素(j)赋值给后一个元素(j+1/temp)
}else { // 后前一个元素小于后一个元素
break; // 当前面一个元素比后面小的时候，就证明前面已经是有序的了，就不需要排序了，直接退出循环
}
} // 出循环，j--
array[j+1] = temp; // 用 temp 覆盖 j 的前一个元素
} // 出循环，i++
}
public static void main(String[] args) {
InsertSort sort = new InsertSort();
int[] array = {12,45,32,56,8};
sort.iSort(array);
System.out.println(Arrays.toString(array));
}
}
输出结果：
稳定性：稳定
时间复杂度：O(n^2)
希尔排序
插入排序的一种优化. 每次排序前进行分组，每组采用插入排序. 每次分组会越来越少.直到分为一组
代码实现：
public class SellSort {
public void sellSort(int[] array){
int grp = array.length; // grp 为分多少组，先分 array.length 组
while (grp > 1){ // 缩小增量
sell(array,grp);
grp /= 2; // 每次排序完对数组再分半
}
// 整体进行插入排序
sell(array,1); // 最终会将 grp 分为一组
}
private void sell(int[] array,int grp) { // 希尔排序，进行分组排序. 每组采用插入排序
for (int i = grp; i < array.length; i++) {
int temp = array[i];
int j = i-grp;
for (; j >= 0; j -= grp) {
if (array[j] > temp){
array[j+grp] = array[j];
}else {
break;
}
}
array[j+grp] = temp;
}
}
public static void main(String[] args) {
SellSort sort = new SellSort();
int[] array = {12,45,32,56,8,22};
sort.sellSort(array);
System.out.println(Arrays.toString(array));
}
}
输出结果：
稳定性：不稳定
时间复杂度： O(n^1.3) - O(n^1.5)
选择排序
第一种：
算法描述：
- 定义两个下标(i，j)，i 为第一个元素下标，j 为后一个元素下标.
- 循环开始时将 i 下标存到 minIndex 中， j 往后循环，过程中找到比 i 下标元素小的下标放到 minIndex 中
- 当 j 循环完，将 i 位置的元素与 minIndex 位置的元素进行交换.
- i++ ，重复如上循环.
代码实现:
/*
* 选择排序第一种方法
* */
public void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int minIndex = i;
int j = i+1; // j 为 i 的前一个
for (; j <array.length ; j++) {
if (array[j] < array[minIndex]) { // 如果当前 j 位置的元素小于 minIndex 下标的元素，就将 j 赋值给 minIndex
minIndex = j;
}
}
swap(array,i,minIndex);
}
}
private void swap(int[] array,int i,int minIndex){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
public static void main(String[] args) {
SelectSort sort = new SelectSort();
int[] array = {12,45,32,56,8};
sort.selectSort(array);
System.out.println("第一种方法排序：" + Arrays.toString(array));
int[] array2 = {77,21,45,6,41};
sort.selectSort2(array2);
System.out.println("第二种方法排序：" + Arrays.toString(array2));
}
输出结果：
第二种：
算法描述：直接看代码注释更加明了.
代码实现：
/*
* 选择排序第二种方法
* */
public void selectSort2(int[] array){
int left = 0; // 定义一个 left 下标（数组第一个元素）
int right = array.length-1; // 定义一个 right下标(数组最后一个元素)
while (left < right){
int minIndex = left; // 假设最小元素的下标为 left
int maxIndex = left; // 假设最大元素的下标为 left
for (int i = left+1; i <= right; i++) {
if (array[i] < array[minIndex]){ // i 下标元素小于 minIndex 下标元素
minIndex = i;
}
if (array[i] > array[maxIndex]) { // i 下标元素大于 maxIndex 下标元素
maxIndex = i;
}
}
// i 循环结束. 进行交换，元素值小放左边，元素值大放右边
swap(array,minIndex,left);
if (maxIndex == left){ // 特殊情况. 当最大元素为数组第一个元素时(left)，此时 minIndex 与 left 进行交互时会将 maxIndex 记录的最大值下标替换掉,改为记录 minIndex.
maxIndex = minIndex;
}
swap(array,maxIndex,right);
left++;
right--;
}
}
输出结果：
稳定性：不稳定
时间复杂度：O(n^2)
堆排序
先将数组转换成一个大根堆，再由大根堆进行排序.
创建大根堆
算法描述：
- 定义一个循环，循环初始值为 parent（父亲结点）= (useSize-1-1)/2.（其中 useSize 为待排序数组的大小）
- 定义一个 child（孩子结点）.其中 child 结点一定是左右孩子中最大的结点.将这两个结点进行比较，大的结点就会被放到 parent 结点的位置.
- 将 parent 移向 child 的位置，child 移向 （parent*2+1） 的位置，继续判断以 child 为根结点下面的树是否为大根堆.
- 上述 parent 一直减减，直到 parent 为 0，大根堆就创建好了
代码实现：
public class HeapSort {
public int[] elem; // 被创建堆的数组（堆底层就是一个数组）
public int useSize; // 记录数组中元素个数
public HeapSort(){
this.elem = new int[10]; // 设定数组大小为10
}
public void initElem(int[] array){ // 初始化 数组
for (int i = 0; i < array.length; i++) {
elem[i] = array[i];
useSize++; // 记录 elem 中有多少个元素，即为 elem 数组大小
}
}
public void createHeap(){ // 创建大根堆
for (int parent = (useSize-1-1)/2; parent >= 0; parent--) { // useSize-1 是数组最后一个元素下标. 再 (-1) / 2 是其根节点的下标
shiftDown(parent,useSize);
}
}
private void shiftDown(int parent, int len) { // 创建大根堆的具体方法
int child = parent*2+1; // 二叉树中左孩子下标
while (child < len){ // 即保证这个二叉树有左孩子
if (child+1 < len && elem[child] < elem[child+1]){ // 在有右孩子的情况下，判断右孩子是否比左孩子大. 其中 child 永远是左右孩子最大值的下标
child++; // 将 child 移向右孩子
}
if(elem[child] > elem[parent]){ // 孩子结点比父亲结点大
// 进行交换
int temp = elem[child];
elem[child] = elem[parent];
elem[parent]= temp;
// 将 parent 移到 child 这里，继续判断以 child 为根结点下面的树是否为大根堆
parent = child;
child = parent*2+1;
}else { // 孩子结点没父亲结点大
break; // 下面的树已经是大根堆了，无需操作
}
}
}
public static void main(String[] args) {
/*
* 测试创建大根堆
* */
HeapSort elem = new HeapSort();
int[] array = {27,15,19,18,28,33,66,50,25,38};
elem.initElem(array); // 初始化数组
elem.createHeap(); // 根据初始数组创建大根堆
System.out.println("dd"); // 调试查看结果
/*
* 测试堆排序
* */
elem.heapSort();
System.out.println("cc");
}
}
输出结果：展开为大根堆
进行堆排序
算法描述：看图和代码注释更加明了.
代码实现：
/*
* 进行堆排序
* 使用大根堆进行排序
* */
public void heapSort(){
int end = useSize - 1;
while (end > 0){ // 当 end 等于0的时候，此时已经有序了，没必要再进行比较了
swap(elem,0,end); // 将最后一个位置的元素与堆顶元素交换
shiftDown(0,end); // 交换后，以第一个元素为 parent ，调整大根堆
end--; //
}
}
private void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
输出结果：
标签：minIndex,Java,temp,int,元素,算法,下标,array,排序 From： https://blog.csdn.net/m0_64304792/article/details/137022602稳定性：不稳定
时间复制度：O(n* )