建站系统推荐,新版wordpress如何添加标签,宝安品牌网站建设,租房子做民宿在哪个网站目录 引言1. 插入排序1.1 基本思想1.2 直接插入排序1.3 希尔排序 2. 选择排序2.1 基本思想2.2 直接选择排序2.3 直接选择排序变种2.4 堆排序 3. 交换排序3.1 基本思想3.2 冒泡排序3.3 快速排序3.3.1 快速排序的基本结构3.3.2 Hoare法3.3.3 挖坑法3.3.4 双指针法 3.4 快速排序非… 目录 引言1. 插入排序1.1 基本思想1.2 直接插入排序1.3 希尔排序 2. 选择排序2.1 基本思想2.2 直接选择排序2.3 直接选择排序变种2.4 堆排序 3. 交换排序3.1 基本思想3.2 冒泡排序3.3 快速排序3.3.1 快速排序的基本结构3.3.2 Hoare法3.3.3 挖坑法3.3.4 双指针法 3.4 快速排序非递归法3.5 快速排序分析 4. 归并排序4.1 基本思想4.1 归并排序递归4.2 归并排序非递。 5. 不基于比较的排序5.1 计数排序 6. 总结 引言
在一些场景中我们需要对数据进行排序就如之前提到的冒泡排序这篇文章将讲述一些主流的排序算法。
1. 插入排序
1.1 基本思想
插入排序的基本思想是将数组分为已排序和未排序两部分逐步将未排序部分的元素插入到已排序部分的适当位置直到整个数组有序。
1.2 直接插入排序
// 插入排序
public static void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];int j i - 1;for (; j 0; j--) {if (array[j] tmp) {array[j 1] array[j];} else {break;}}array[j 1] tmp;}
}从数组的第二个元素开始索引为1认为第一个元素是已排序的。 取出当前元素 tmp并将其与已排序部分的元素从后向前比较。如果已排序部分的元素大于 tmp则将该元素向后移动一位。重复上述步骤直到找到一个不大于 tmp 的元素位置。将 tmp 插入到该位置。重复步骤2-5直到所有元素都插入到已排序部分。
时间复杂度O(n2) 空间复杂度O(1) 稳定性稳定
1.3 希尔排序
希尔排序的基本思想是通过将数组分成若干子序列分别进行插入排序从而加快排序速度。它是对直接插入排序的一种改进。
// 希尔排序
public static void shellSort(int[] array) {int gap array.length / 2;while (gap 0) {shell(array, gap);gap / 2;}
}public static void shell(int[] array, int gap) {for (int i gap; i array.length; i) {int tmp array[i];int j i - gap;for (; j 0; j - gap) {if (array[j] tmp) {array[j gap] array[j];} else {break;}}array[j gap] tmp;}
}shellSort 方法初始化间隔 gap 为数组长度的一半。在 gap 大于0的情况下调用 shell 方法对数组进行分组排序然后将 gap 减半。shell 方法对每个间隔为 gap 的子序列进行插入排序。在 shell 方法中从索引 gap 开始取出当前元素 tmp并将其与间隔为 gap 的已排序部分的元素从后向前比较。如果已排序部分的元素大于 tmp则将该元素向后移动 gap 位。重复上述步骤直到找到一个不大于 tmp 的元素位置。将 tmp 插入到该位置。重复步骤4-7直到所有子序列都排序完成。
希尔排序由于gap值不确定时间复杂度并没有确切的值但是时间复杂度是比直接插入排序要低的。 空间复杂度O(1) 稳定性不稳定
2. 选择排序
2.1 基本思想
每⼀次从待排序的数据元素中选出最⼩或最⼤的⼀个元素存放在序列的起始位置直到全部待 排序的数据元素排完。
2.2 直接选择排序
// 选择排序
public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;for (int j i 1; j array.length; j) {if (array[j] array[minIndex]) {minIndex j;}}if (minIndex ! i) {swap(array, i, minIndex);}}
}// 辅助方法交换数组中的两个元素
private static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;
}从数组的第一个元素开始认为第一个元素是已排序的。在未排序部分中找到最小的元素并记录其索引 minIndex。将最小元素与当前元素交换位置如果 minIndex 不等于当前索引 i。重复步骤2-3直到所有元素都排序完成。
时间复杂度O(n2) 空间复杂度O(1) 稳定性不稳定
2.3 直接选择排序变种
直接选择排序的变种在每一趟排序中同时找到未排序部分的最小值和最大值并分别将它们放到未排序部分的两端。
public static void selectSort2(int[] array) {int left 0;int right array.length - 1;while (left right) {int minIndex left;int maxIndex left;for (int i left 1; i right; i) {if (array[i] array[minIndex]) {minIndex i;}if (array[i] array[maxIndex]) {maxIndex i;}}if (minIndex ! left) {swap(array, minIndex, left);}if (maxIndex left) {maxIndex minIndex;}if (maxIndex ! right) {swap(array, maxIndex, right);}left;right--;}
}// 辅助方法交换数组中的两个元素
private static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;
}初始化两个指针 left 和 right分别指向数组的两端。在未排序部分中找到最小值和最大值的索引 minIndex 和 maxIndex。将最小值与 left 位置的元素交换。如果最大值的索引是 left则更新 maxIndex 为 minIndex因为最小值已经被交换到 left 位置。将最大值与 right 位置的元素交换。移动 left 和 right 指针缩小未排序部分的范围。重复步骤2-6直到 left 和 right 相遇。
2.4 堆排序
堆排序是一种基于堆数据结构的排序算法利用堆的性质来排序数组。
// 堆排序
public static void heapSort(int[] array) {createHeap(array);int end array.length - 1;while (end 0) {swap(array, 0, end);siftDown(array, 0, end);end--;}
}// 创建最大堆
public static void createHeap(int[] array) {for (int p (array.length - 1 - 1) / 2; p 0; p--) {siftDown(array, p, array.length);}
}// 向下调整堆
private static void siftDown(int[] array, int p, int length) {int c 2 * p 1;while (c length) {if (c 1 length array[c] array[c 1]) {c;}if (array[c] array[p]) {swap(array, c, p);p c;c 2 * p 1;} else {break;}}
}// 辅助方法交换数组中的两个元素
private static void swap(int[] array, int i, int j) {int temp array[i];array[i] array[j];array[j] temp;
}创建最大堆调用 createHeap 方法将数组转换为最大堆。 从最后一个非叶子节点开始向上逐个节点进行向下调整siftDown确保每个子树都是最大堆。排序过程 将堆顶元素最大值与当前未排序部分的最后一个元素交换。调整堆顶元素使剩余部分重新成为最大堆siftDown。缩小未排序部分的范围重复上述步骤直到整个数组有序。时间复杂度O(nlogn) 空间复杂度O(1) 稳定性不稳定
3. 交换排序
3.1 基本思想
交换排序的基本思想是通过比较和交换数组中的元素使数组逐步有序。
3.2 冒泡排序
冒泡排序通过重复地遍历数组每次比较相邻的两个元素如果它们的顺序错误就交换它们的位置。这样每一趟遍历都会将当前未排序部分的最大元素“冒泡”到数组的末尾。重复这个过程直到整个数组有序。 //冒泡排序public static void bubbleSort(int[] array) {for (int i 0; i array.length; i) {boolean flg true;for (int j 0; j array.length - i - 1; j) {if (array[j] array[j 1]) {swap(array, j, j 1);flg false;}}if (flg) {break;}}}外层循环遍历数组的每一个元素控制排序的趟数。内层循环从数组的第一个元素开始比较相邻的两个元素如果前一个元素大于后一个元素就交换它们的位置。标志变量 flg用于检测当前趟排序是否发生了交换。如果在某一趟排序中没有发生交换说明数组已经有序可以提前结束排序。交换函数 swap用于交换数组中的两个元素。
时间复杂度O(n2) 空间复杂度O(1) 稳定性稳定
3.3 快速排序
快速排序的基本思想是通过选择一个枢轴元素将数组分成两部分使得左侧部分的所有元素都小于枢轴右侧部分的所有元素都大于枢轴。然后递归地对左右两部分进行快速排序直到整个数组有序。快速排序有多种排序方法先介绍基本结构。
3.3.1 快速排序的基本结构
public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}public static void quick(int[] array, int left, int right) {if (left right) {return;}int index partition(array, left, right);quick(array, left, index - 1);quick(array, index 1, right);}快速排序入口方法 (quickSort) 这是快速排序的入口方法接收一个数组 array 作为参数。调用 quick 方法对整个数组进行排序初始的左右边界分别是 0 和 array.length - 1。递归排序方法 (quick) 这是快速排序的递归方法用于对数组的某个子区间进行排序。
参数 left 和 right 分别表示当前子区间的左边界和右边界。
基本条件如果 left 大于或等于 right说明当前子区间已经有序或只有一个元素直接返回。
调用 partition 方法将数组分成两部分并返回枢轴元素的位置 index。
递归地对左侧部分left 到 index - 1进行排序。
递归地对右侧部分index 1 到 right进行排序。下面介绍partition的各种实现方法
3.3.2 Hoare法
Hoare法的partition分区算法是快速排序中的一种分区方法。它通过选择一个枢轴元素将数组分成两部分使得左侧部分的所有元素都小于等于枢轴右侧部分的所有元素都大于等于枢轴。 private static int partition1(int[] array, int left, int right) {int i left;int j right;int pivot array[left];while (i j) {while (i j array[j] pivot) {j--;}while (i j array[i] pivot) {i;}swap(array, i, j);}swap(array, i, left);return i;}选择枢轴 选择最左边的元素作为枢轴pivot。初始化指针 初始化两个指针 i 和 j分别指向数组的左边界和右边界。分区过程 使用两个 while 循环分别从右向左和从左向右扫描数组从右向左找到第一个小于枢轴的元素更新指针 j。从左向右找到第一个大于枢轴的元素更新指针 i。如果 i 小于 j交换 i 和 j 指向的元素。重复上述过程直到 i 和 j 相遇或交错。交换枢轴 将枢轴元素放到正确的位置即 i 位置。返回 i 作为分区点。3.3.3 挖坑法 public static int partition(int[] array, int left, int right) {int base array[left];int i left;int j right;while (i j) {while (i j array[j] base) {j--;}array[i] array[j];while (i j array[i] base) {i;}array[j] array[i];}array[i] base;return i;}选择枢轴 选择最左边的元素作为枢轴base。初始化指针 初始化两个指针 i 和 j分别指向数组的左边界和右边界。分区过程 使用两个 while 循环分别从右向左和从左向右扫描数组从右向左找到第一个小于枢轴的元素更新指针 j并将该元素放到 i 位置。从左向右找到第一个大于枢轴的元素更新指针 i并将该元素放到 j 位置。重复上述过程直到 i 和 j 相遇或交错。交换枢轴 将枢轴元素放到正确的位置即 i 位置。返回 i 作为分区点。3.3.4 双指针法 private static int partition(int[] array, int left, int right) {int prev left;int cur left 1;while (cur right) {if (array[cur] array[left] array[prev] ! array[cur]) {swap(array, cur, prev);}cur;}swap(array, prev, left);return prev;}选择枢轴 选择最左边的元素作为枢轴array[left]。初始化指针 初始化两个指针 prev 和 cur分别指向数组的左边界和枢轴的下一个位置。分区过程 使用 while 循环从 cur 指针开始遍历数组直到 cur 超过右边界 right。如果 cur 指针指向的元素小于枢轴元素并且 prev 指针和 cur 指针指向的元素不同则交换 cur 和 prev 指针指向的元素。每次交换后prev 指针向右移动一位。cur 指针每次循环后向右移动一位。交换枢轴 将枢轴元素放到正确的位置即 prev 位置。返回 prev 作为分区点。3.4 快速排序非递归法
非递归快速排序通过使用栈来模拟递归调用从而避免了递归带来的栈溢出问题。 public static void quickSortNonR(int[] a, int left, int right) {StackInteger st new Stack();st.push(left);st.push(right);while (!st.empty()) {right st.pop();left st.pop();if (right - left 1) {continue;}int div partition(a, left, right);st.push(div 1);st.push(right);st.push(left);st.push(div);}}初始化栈 创建一个栈 st用于存储数组的左右边界。将初始的左右边界 left 和 right 压入栈中。循环处理 当栈不为空时循环执行以下步骤从栈中弹出 right 和 left表示当前需要处理的子数组的左右边界。如果子数组的长度小于等于1即 right - left 1则跳过当前循环继续处理下一个子数组。调用 partition 方法对当前子数组进行分区返回枢轴位置 div。将右侧子数组的左右边界div 1 和 right压入栈中。将左侧子数组的左右边界left 和 div压入栈中。分区方法 partition 方法用于将数组分成两部分使得左侧部分的所有元素都小于等于枢轴右侧部分的所有元素都大于等于枢轴。3.5 快速排序分析
时间复杂度O(nlogn) 空间复杂度O(logn) 稳定性不稳定
4. 归并排序
归并排序是一种基于分治法的排序算法。它将数组分成两个子数组分别对这两个子数组进行排序然后将排序后的子数组合并成一个有序的数组。
4.1 基本思想
分解将数组分成两个子数组分别对这两个子数组进行排序。递归排序递归地对每个子数组进行归并排序。合并将两个有序的子数组合并成一个有序的数组。
4.1 归并排序递归
// 归并排序
public static void mergeSort(int[] array) {mergeSortChild(array, 0, array.length - 1);
}// 递归排序子数组
public static void mergeSortChild(int[] array, int left, int right) {if (left right) {return;}int mid (left right) / 2;mergeSortChild(array, left, mid);mergeSortChild(array, mid 1, right);merge(array, left, mid, right);
}// 合并两个有序子数组
public static void merge(int[] array, int left, int mid, int right) {int s1 left;int s2 mid 1;int[] tmp new int[right - left 1];int i 0;while (s1 mid s2 right) {if (array[s1] array[s2]) {tmp[i] array[s1];} else {tmp[i] array[s2];}}while (s1 mid) {tmp[i] array[s1];}while (s2 right) {tmp[i] array[s2];}for (int j 0; j tmp.length; j) {array[left j] tmp[j];}
}归并排序入口方法 (mergeSort) 这是归并排序的入口方法接收一个数组 array 作为参数。调用 mergeSortChild 方法对整个数组进行排序初始的左右边界分别是 0 和 array.length - 1。递归排序子数组 (mergeSortChild) 这是归并排序的递归方法用于对数组的某个子区间进行排序。参数 left 和 right 分别表示当前子区间的左边界和右边界。基本条件如果 left 大于或等于 right说明当前子区间已经有序或只有一个元素直接返回。计算中间位置 mid将数组分成两部分。递归地对左侧部分left 到 mid进行排序。递归地对右侧部分mid 1 到 right进行排序。调用 merge 方法将两个有序的子数组合并成一个有序的数组。合并两个有序子数组 (merge) 参数 left、mid 和 right 分别表示当前子区间的左边界、中间位置和右边界。初始化两个指针 s1 和 s2分别指向两个子数组的起始位置。创建一个临时数组 tmp用于存储合并后的有序数组。使用 while 循环将两个子数组中的元素按顺序合并到临时数组 tmp 中。将剩余的元素如果有复制到临时数组 tmp 中。将临时数组 tmp 中的元素复制回原数组 array 中。时间复杂度O(nlogn) 空间复杂度O(n) 稳定性稳定
4.2 归并排序非递。
非递归归并排序也称为迭代归并排序通过逐步增加子数组的大小来实现排序。 public static void mergeSortNoR(int[] array) {int gap 1;while(gap array.length) {for (int i 0; i array.length; i 2 * gap) {int left i;int mid left gap - 1;if(mid array.length - 1) {mid array.length - 1;}int right mid gap;if(right array.length) {right array.length - 1;}merge(array, left, mid, right);}gap * 2;}} 初始化间隔 (gap) 初始化间隔 gap 为1表示初始的子数组大小为1。外层循环 当 gap 小于数组长度时继续循环。每次循环将 gap 翻倍表示子数组的大小逐步增加。内层循环 遍历数组将数组分成若干个大小为 2 * gap 的子数组。计算每个子数组的左边界 left、中间位置 mid 和右边界 right。调用 merge 方法将两个有序的子数组合并成一个有序的数组。5. 不基于比较的排序
不基于比较的排序算法主要包括计数排序、基数排序和桶排序。这些算法不通过比较元素来排序而是利用元素的值来确定其位置从而实现线性时间复杂度的排序。这里就介绍计数排序。
5.1 计数排序
计数排序适用于元素值范围较小的情况。它通过统计每个元素出现的次数然后根据这些计数来确定每个元素的位置。
public static void countingSort(int[] array) {int max array[0];int min array[0];// 找到数组中的最大值和最小值for (int i 1; i array.length; i) {if (array[i] max) {max array[i];}if (array[i] min) {min array[i];}}// 创建计数数组int len max - min 1;int[] countArray new int[len];// 统计每个元素出现的次数for (int i 0; i array.length; i) {int index array[i] - min;countArray[index];}// 根据计数数组重新填充原数组int k 0;for (int i 0; i countArray.length; i) {while (countArray[i] 0) {array[k] i min;countArray[i]--;}}
}找到最大值和最小值 遍历数组找到数组中的最大值 max 和最小值 min。创建计数数组 根据最大值和最小值计算计数数组的长度 len即 max - min 1。创建一个长度为 len 的计数数组 countArray用于统计每个元素出现的次数。统计每个元素出现的次数 遍历原数组对于每个元素 array[i]计算其在计数数组中的索引 index即 array[i] - min。将计数数组中对应位置的值加1表示该元素出现了一次。根据计数数组重新填充原数组 遍历计数数组对于每个非零的计数值将对应的元素填充回原数组。使用一个指针 k 来记录当前填充的位置。对于计数值 countArray[i]将元素 i min 填充回原数组 countArray[i] 次。6. 总结
以上就是一些常用的排序算法的介绍和代码实现具体如何排序可以看这里的链接 十大经典排序算法动画与解析。
