跳到主要内容 常见排序算法详解与 Java 实现 | 极客日志
Java java 算法
常见排序算法详解与 Java 实现 多种常见排序算法的原理及 Java 实现,包括插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序(含 Hoare、挖坑法、前后指针法及非递归版)、归并排序(递归与非递归)以及计数排序。文章提供了各算法的时间复杂度、空间复杂度分析及稳定性说明,并附有完整的 Java 代码示例,适合算法学习与面试准备。
PhpPioneer 发布于 2026/3/27 更新于 2026/4/16 5 浏览常见排序算法详解与 Java 实现
声明:以下排序代码由 Java 实现。
插入排序
步骤:
我们可以认为数组的第一个元素已经被排好序,因此只需考虑对后面的元素进行插入排序;
取下一个位置的元素 val,让它和它之前的元素进行比较,顺序为从右向左;
如果该元素大于 val,则将该元素移动到该元素所处位置的下一个位置;
重复步骤 3,直到找到已排好序的序列中小于等于 val 的元素;
将值 val 放到该位置的下一个位置,如果已排好序的所有元素的值都大于 val,则将 val 存放到数组下标为 0 的位置;
重复 2~5 步骤。
代码如下:
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;
}
}
折半插入排序
在该值为 val 的元素找合适的位置时,是在已排好序的序列中进行找的,因此该过程可以使用二分查找(折半查找)来进行优化。
代码如下:
public static void bsInsertSort (int [] array) {
for (int i = 0 ; i < array.length; i++) {
array[i];
, right = i;
(left < right) {
(left + right) >> ;
(tmp >= array[mid]) {
left = mid + ;
} {
right = mid;
}
}
( i; j > left; j--) {
array[j] = array[j - ];
}
array[left] = tmp;
}
}
微信扫一扫,关注极客日志 微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具 Keycode 信息 查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
Escape 与 Native 编解码 JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
JavaScript / HTML 格式化 使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
JavaScript 压缩与混淆 Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
int
tmp
=
int
left
=
0
while
int
mid
=
1
if
1
else
for
int
j
=
1
时间复杂度:最好情况下为 O(N),此时待排数组为升序,或者说非常接近升序;最坏情况下为 O(N^2),此时待排数组为降序,或者说非常接近降序。
空间复杂度:O(1)
稳定性:稳定
希尔排序(缩小增量排序) 先选定一个小于 N 的整数 gap 作为第一增量,然后将所有距离为 gap 的元素划分在同一组,对每组的元素进行直接插入排序,然后再选取一个比第一增量小的整数作为第二增量 gap,然后将所有距离为 gap 的元素划分在同一组,对每组的元素进行直接插入排序,以此类推.........,直到增量减小为 1 时,此时就相当于整个数组被划分为一组,进行一次直接插入排序即可。
增量 gap 大于 1 时,称为'预排序',使得待排数组接近有序;增量 gap 为 1 时,称为直接插入排序。
public static void shellSort (int [] array) {
int gap = array.length;
while (gap > 1 ) {
gap = gap / 3 + 1 ;
shell(array, gap);
}
}
private 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;
}
}
平均时间复杂度:O(N^1.3)
空间复杂度:O(1)
选择排序 每一次从待排序列中选出最小(或者最大)的一个元素,存放在待排序列的起始位置,同时将待排序列原来起始位置的值放到待排序列中最小元素的位置,直到待排数据全部排完序。
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;
}
}
swap(array, i, minIndex);
}
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
实际上,我们可以每一趟同时选择出待排序列中的最小值和最大值,然后将最小值放待排序列起始位置,将最大值放到待排序列的末尾,直到待排数据全部排完序,这样的话比前一种方法快一倍。
public static void DoubleSelectSort (int [] array) {
int left = 0 , right = array.length - 1 ;
while (left < right) {
int minIndex = left, maxIndex = left;
for (int i = left + 1 ; i <= right; i++) {
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
if (array[i] < array[minIndex]) {
minIndex = i;
}
}
swap(array, left, minIndex);
if (maxIndex == left) {
maxIndex = minIndex;
}
swap(array, right, maxIndex);
left++;
right--;
}
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
冒泡排序 进行 N 趟,每一趟中,如果前一个位置的元素大于后一个位置的元素,则交换两个位置的元素。
public static void bubbleSort (int [] array) {
for (int i = 0 ; i < array.length; i++) {
boolean flag = false ;
for (int j = 0 ; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1 ]) {
swap(array, j, j + 1 );
flag = true ;
}
}
if (!flag) {
break ;
}
}
}
堆排序 以排升序为例,先对数组建立大根堆,然后将堆顶元素和堆最后一个元素交换,然后从堆顶进行向下调整,不过此时堆的大小要 -1,因为已经把最大的元素找出来并放在数组的末尾了,不断重复上述操作,直到将整个数组的元素排完序。
public static void heapSort (int [] array) {
createBigHeap(array);
int end = array.length - 1 ;
while (end > 0 ) {
swap(array, 0 , end);
shiftDown(array, 0 , end);
end--;
}
}
private static void createBigHeap (int [] array) {
for (int parent = array.length - 1 - 1 ; parent >= 0 ; parent--) {
shiftDown(array, parent, array.length);
}
}
private static void shiftDown (int [] array, int parent, int end) {
int child = 2 * parent + 1 ;
while (child < end) {
if (child + 1 < end && array[child + 1 ] > array[child]) {
child++;
}
if (array[parent] < array[child]) {
swap(array, parent, child);
parent = child;
child = 2 * parent + 1 ;
} else {
break ;
}
}
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
时间复杂度:O(N*logN)
空间复杂度:O(1)
快速排序
Hoare 版
选定一个值 Key,下标记为 Keyi,通常是最左边的元素或者最右边的元素;
定义两个指针 begin 和 end,begin 从左往右走,end 从右往左走;
若选定的 Key 值是最左边的元素,需要 end 先走,若选定的 Key 值是最右边的元素,需要 begin 先走;
在走的过程中,当 end 遇到小于 Key 的数,才停下;然后 begin 开始走,直到遇到大于 Key 的数,然后交换位于 begin 和 end 位置的值,然后 end 再走,规则如上,直到 begin 和 end 相遇,此时再将位于 Keyi 位置的 Key 值和 begin 和 end 相遇点的值进行交换;
此时,Key 左边的值都是小于等于 Key 的数,Key 右边的值都是大于等于 Key 的数;
然后再对 Key 左边的数以及 Key 右边的数分别进行如上操作,直到待排序列只有一个元素为止。
因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】
public static void quickSort (int [] array) {
quick(array, 0 , array.length - 1 );
}
private static void quick (int [] array, int start, int end) {
if (start >= end) {
return ;
}
if (end - start <= 7 ) {
insertSortRange(array, start, end);
return ;
}
int pivot = partitionHoare(array, start, end);
quick(array, start, pivot - 1 );
quick(array, pivot + 1 , end);
}
private static void insertSortRange (int [] array, int begin, int end) {
for (int i = begin + 1 ; i <= end; i++) {
int tmp = array[i];
int j = i - 1 ;
for (; j >= begin; j--) {
if (array[j] > tmp) {
array[j + 1 ] = array[j];
} else {
break ;
}
}
array[j + 1 ] = tmp;
}
}
private static int midOfThree (int [] array, int left, int right) {
int mid = (left + right) / 2 ;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
}
}
private static int partitionHoare (int [] array, int left, int right) {
int key = array[left];
int keyi = left;
while (left < right) {
while (left < right && array[right] >= key) {
right--;
}
while (left < right && array[left] <= key) {
left++;
}
swap(array, left, right);
}
swap(array, keyi, left);
return left;
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
时间复杂度:O(N*logN)
空间复杂度:O(1)
挖坑法
选定一个 Key 值,通常是位于最左边或者是最右边,在该位置形成一个坑;
定义两个指针 left 和 right,left 从左向右走,right 从右向左走;
如果 Key 值位于数组最左边,需要 right 先走;如果 Key 值位于数组最右边,需要 left 先走;
在走的过程中,当 end 遇到小于 Key 的数,才停下,然后将 right 位置的值填放到坑位置,此时 right 位置处形成一个坑;然后 begin 开始走,直到遇到大于 Key 的数,然后将 left 位置的值填放到坑位置,此时 left 位置处形成一个坑;然后 right 再走,规则如上,直到 left 和 right 相遇,此时再将位于 Key 值填放到坑位置处;
此时,Key 左边的值都是小于等于 Key 的数,Key 右边的值都是大于等于 Key 的数;
然后再对 Key 左边的数以及 Key 右边的数分别进行如上操作,直到待排序列只有一个元素为止。
因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】
public static void quickSort (int [] array) {
quick(array, 0 , array.length - 1 );
}
private static void quick (int [] array, int start, int end) {
if (start >= end) {
return ;
}
if (end - start <= 7 ) {
insertSortRange(array, start, end);
return ;
}
int pivot = partitionHole(array, start, end);
quick(array, start, pivot - 1 );
quick(array, pivot + 1 , end);
}
private static void insertSortRange (int [] array, int begin, int end) {
for (int i = begin + 1 ; i <= end; i++) {
int tmp = array[i];
int j = i - 1 ;
for (; j >= begin; j--) {
if (array[j] > tmp) {
array[j + 1 ] = array[j];
} else {
break ;
}
}
array[j + 1 ] = tmp;
}
}
private static int midOfThree (int [] array, int left, int right) {
int mid = (left + right) / 2 ;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
}
}
private static int partitionHole (int [] array, int left, int right) {
int key = array[left];
while (left < right) {
while (left < right && array[right] >= key) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= key) {
left++;
}
array[right] = array[left];
}
array[left] = key;
return left;
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
时间复杂度:O(N*logN)
空间复杂度:O(1)
前后指针法
选定数组最左边的值为基准值;
定义两个指针 prev 和 cur,开始时 prev 在最左边,cur 在 prev 的下一个位置;
让 cur 向右走,如果 cur 位置的值大于基准值,只需 cur 继续向右移动,直到遇到比基准值小的值;
如果 cur 位置的值小于基准值,先让 prev 向右移动一个位置,然后交换 prev 位置的值和 cur 位置的值,直到 cur 走到数组末尾。
因为该方法包含大量的递归,当数据量较大时会发生栈溢出,因此做一些优化,包括【三数取中】和【当待排区间长度小于某个常数时,不再递归进行快排,而是使用直接插入排序】
public static void quickSort (int [] array) {
quick(array, 0 , array.length - 1 );
}
private static void quick (int [] array, int start, int end) {
if (start >= end) {
return ;
}
if (end - start <= 7 ) {
insertSortRange(array, start, end);
return ;
}
int pivot = partitionDouble(array, start, end);
quick(array, start, pivot - 1 );
quick(array, pivot + 1 , end);
}
private static void insertSortRange (int [] array, int begin, int end) {
for (int i = begin + 1 ; i <= end; i++) {
int tmp = array[i];
int j = i - 1 ;
for (; j >= begin; j--) {
if (array[j] > tmp) {
array[j + 1 ] = array[j];
} else {
break ;
}
}
array[j + 1 ] = tmp;
}
}
private static int midOfThree (int [] array, int left, int right) {
int mid = (left + right) / 2 ;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[left]) {
return left;
} else if (array[mid] < array[right]) {
return right;
} else {
return mid;
}
}
}
private static int partitionDouble (int [] array, int left, int right) {
int prev = left, cur = prev + 1 ;
while (cur <= right) {
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, prev, cur);
}
cur++;
}
swap(array, prev, left);
return prev;
}
private static void swap (int [] array, int i, int j) {
int ret = array[i];
array[i] = array[j];
array[j] = ret;
}
时间复杂度:O(N*logN)
空间复杂度:O(1)
非递归版 public static void quickSortNor (int [] array) {
Stack<Integer> stack = new Stack <>();
int left = 0 ;
int right = array.length - 1 ;
int piovt = partitionHole(array, left, right);
if (piovt - 1 > left) {
stack.push(left);
stack.push(piovt - 1 );
}
if (piovt + 1 < right) {
stack.push(piovt + 1 );
stack.push(right);
}
while (!stack.isEmpty()) {
right = stack.pop();
left = stack.pop();
piovt = partitionHole(array, left, right);
if (piovt - 1 > left) {
stack.push(left);
stack.push(piovt - 1 );
}
if (piovt + 1 < right) {
stack.push(piovt + 1 );
stack.push(right);
}
}
}
归并排序
递归版 使用递归不断将区间二分,直到区间只有一个元素为止,然后将两个区间进行排序合并,直到将所有区间合并完。
public static void mergeSort (int [] array) {
int [] dst = new int [array.length];
dst = Arrays.copyOf(array, array.length);
merge(array, dst, 0 , array.length - 1 );
for (int i = 0 ; i < array.length; i++) {
array[i] = dst[i];
}
}
private static void merge (int [] src, int [] dst, int start, int end) {
if (start >= end) {
return ;
}
int mid = (start + end) >> 1 ;
merge(dst, src, start, mid);
merge(dst, src, mid + 1 , end);
int i = start, j = mid + 1 , k = start;
while (i <= mid || j <= end) {
if (j > end || (i <= mid && src[i] < src[j])) {
dst[k++] = src[i++];
} else {
dst[k++] = src[j++];
}
}
}
时间复杂度:O(N*logN)
空间复杂度:O(N)
非递归版 将整个区间划分为长度为 1, 2, 4, 8,..........最大为 N 的小区间,然后对相邻的长度为 1, 2, 4, 8,..........最大为 N 的小区间分别进行排序合并,最终就排好序了。
public static void mergeSortNor (int [] array) {
int [] src = array;
int [] dst = new int [array.length];
for (int step = 1 ; step < array.length; step += step) {
for (int start = 0 ; start < array.length; start += step * 2 ) {
int mid = Math.min(start + step - 1 , array.length - 1 );
int end = Math.min(start + 2 * step - 1 , array.length - 1 );
int i = start, j = mid + 1 , k = start;
while (i <= mid || j <= end) {
if (j > end || (i <= mid && src[i] < src[j])) {
dst[k++] = src[i++];
} else {
dst[k++] = src[j++];
}
}
}
int [] tmp = src;
src = dst;
dst = tmp;
}
for (int i = 0 ; i < array.length; i++) {
array[i] = src[i];
}
}
时间复杂度:O(N*logN)
空间复杂度:O(N)
计数排序 先求出序列中的最大值 maxVal 和最小值 minVal,然后开辟一个长度为 maxVal-minVal+1 的数组,值全都初始化为 0,然后遍历整个数组,将下标为每个位置的值减去 minVal 处的值++,然后再重复将每个位置的值表示的次数次,将对应的值【下标+minVal】存放到原数组中。
public static void countSort (int [] array) {
int minVal = array[0 ];
int maxVal = array[0 ];
for (int i = 1 ; i < array.length; i++) {
if (array[i] < minVal) {
minVal = array[i];
}
if (array[i] > maxVal) {
maxVal = array[i];
}
}
int [] count = new int [maxVal - minVal + 1 ];
for (int i = 0 ; i < array.length; i++) {
count[array[i] - minVal]++;
}
int index = 0 ;
for (int i = 0 ; i < count.length; i++) {
while (count[i] > 0 ) {
array[index] = i + minVal;
index++;
count[i]--;
}
}
}