排序算法(Java)
·
目录
一、排序
1、排序的概念
排序是指将一组无序的数据（如数字、字符、记录等）按照某种特定的规则（称为“排序依据”）重新排列成有序序列的过程。
排序的作用：方便数据的查找，便于数据的统计、分析和展示，是许多算法的基础步骤
稳定性：在排序过程中，对于序列中两个相等的元素，如果排序后它们的相对位置保持不变，则称该排序算法是稳定的，反之则为不稳定。
内部排序：数据元素全部放在内存中的排序
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断的在内外存之间移动数据的排序
2、 排序的应用
3、 常见的排序算法
二、常见排序算法的实现
1、插入排序
插入排序是一种简单直观的排序算法，核心思想是将数组分为 “ 已排序 ” 和 “ 未排序 ”两部分，每次从未排序部分取一个元素，插入到已排序部分的合适位置，直到所有元素都被插入。
1.1 直接插入排序
步骤：
- 第一个元素默认有序
- 从第二个元素开始，用一个变量来得到这个元素的值（依次取未排序元素）
- 拿这个元素的值与已排序部分进行从后往前比，若已排序元素更大，则已排序元素向后移一位，直到找到比该元素小的值（也可能到0下标）
- 将待插元素放入找到的位置
- 重复 2 - 4，直到所有元素都排好
代码展示：
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;
}
}直接插入排序特性总结：
- 元素集合越有序，直接插入排序算法时间效率越高
- 时间复杂度：O(n^2)，最好情况下为O( n )
- 空间复杂度：O( 1 )
- 稳定性：稳定
1.2 希尔排序
步骤：
- 确定初始增量:通常取数组长度的一半(gap=len/2)，后续每次将增量减半(gap/=2)，直到增量为1
- 按增量分组：将数组按当前增量分为若干组，每组下标相差gap为一组，组内进行直接插入排序
- 减小增量重复：重复步骤2，直到增量为1，整个数组被分为1组，执行一次直接插入排序，完成最终排序
代码展示：
public static void shellSort(int[] array){
int gap= array.length;
while(gap>1){
gap/=2;
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.25)~O(n^1.6)
- 空间复杂度：O(1)
- 稳定性：不稳定
- 适用于一些中等规模大小的数据
2、选择排序
选择排序是每一次从待排序元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
2.1 直接选择排序
步骤：
- 从待排序序列的第一个元素开始，假设该元素为当前最小元素，用minIndex记录其位置
- 依次将当前最小元素与序列中后面的每一个元素进行比较，若发现更小的元素则更新minIndex
- 当序列遍历完之后，将找到的最小元素与序列的第一个元素交换位置，此时第一个元素已确认为最小值，成为有序序列的一部分
- 排除有序的元素对剩余的未排序序列重复1~3，直到排序完成
代码展示：
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 tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}直接选择排序特性总结：
- 适用于数据量较少的场景，无论序列是否接近有序，时间复杂度都是O(n^2)
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
2.2 堆排序
步骤：
- 首先我们要知道在堆排序中升序建大堆，降序建小堆
- 将待排序数组视为一个完全二叉树，从最后一个父节点开始，依次向前进行大根堆调整（使父节点的值大于左右两个子节点的值），此时我们就创建好了一个大根堆
- 定义一个变量end指向大根堆的最后一个元素 ，然后交换堆顶与末尾元素，此时最大值已经放到了末尾
- 排除已排好的末尾元素，对剩余的end-1个元素重新进行堆调整，使其再次满足大根堆性质
- 重复3~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--;
}
}
private static void createHeap(int[] array) {
for (int parent = (array.length-2)/2; parent >=0 ; parent--) {
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array, int parent, int length) {
int child=2*parent+1;
while(child<length){
if(child+1<length&&array[child]<array[child+1]){
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 parent, int child) {
int tmp=array[parent];
array[parent]=array[child];
array[child]=tmp;
}堆排序特性总结：
- 适用于数据量较大的场景
- 时间复杂度：O(n*logn)
- 空间复杂度：O(1)
- 稳定性：不稳定
3、交换排序
交换排序是一类通交换元素位置来实现排序的算法，核心思想是比较两个元素的大小，若顺序不符合要求则交换它们的位置，重复这一过程直至序列有序。
3.1 冒泡排序
步骤：
- 对于长度为 n 的序列，最多遍历 n-1 轮即可
- 对初始序列进行多轮遍历，每轮仅处理未确定位置的元素，序列的起始位置开始，依次比较相邻的两个元素，若前者大于后者，交换两者位置
- 每轮结束后，未排序部分的最大元素会到末尾，成为已排序的部分
- 重复上述过程，直至某一轮没有发生任何元素的交换，此时整个序列已有序
代码展示：
public static void bubbleSort(int[] array){
for (int i = 0; i < array.length-1 ; 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;
}
}
}
private static void swap(int[] array, int i, int j) {
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
冒泡排序特性总结：
- 适用于数据量较小的场景
- 时间复杂度：O(n^2)，最好情况O(n)
- 空间复杂度O(1)
- 稳定性：稳定
3.2 快速排序
挖坑法
步骤：
- 选最左侧元素为基准值，其位置作为初始坑，左指针（left）指向起始，右指针（right）指向末尾
- 右指针以基准为基础，找第一个小于基准的元素，填入坑，该元素位置变成新坑，左指针右移
- 然后左指针找第一个比基准大的元素，填入新坑，右指针左移
- 重复步骤2~3，直到左右指针相遇，将基准值填入到相遇位置的坑，此时基准值左边均小于它，右边均大于它
- 对基准值左侧和右侧的子序列分别重复上述步骤，直至子序列长度为1或0，排序完成（递归，也可以使用非递归，但需要用到栈）
代码展示：
private static void quick(int[] array, int left, int right) {
if(left>=right){
return;
}
int par=parttionSpark(array,left,right);//这里的方法为挖坑法可替换
quick(array,left,par-1);
quick(array,par+1,right);
}
private static int parttionSpark(int[] array, int left, int right) {
int tmp=array[left];
while(left<right){
while(left<right && array[right]>=tmp){
right--;
}
array[left]=array[right];
while(left<right && array[left]<=tmp){
left++;
}
array[right]=array[left];
}
array[left]=tmp;
return left;
}Hoare法
步骤：
- 以数组首个元素作为基准值（pivot）
- 右指针从最后一个元素开始，直到遇到第一个比基准值小的元素，然后左指针右移，直到遇到比基准值大的元素
- 交换左指针和右指针指向的元素，重复此过程，直到左指针与右指针相遇
- 交换基准值与左右指针相遇位置的元素
- 对基准值左右两侧的子树组重复上述步骤，直到子数组长度为0或1
代码展示：
private static int parttionHoare(int[]array,int left,int right){
int pivot=array[left];
int i=left;
while (left<right){
while (left<right && array[right]>=pivot){
right--;
}
while (left<right && array[left]<=pivot) {
left++;
}
swap(array,left,right);//交换
}
swap(array,i,left);
return left;
}前后指针
步骤：
- 将首个元素作为基准
- 前驱指针 prev指向 left， 当前指针 cur 指向 left+1
- cur 不能超过 right，若 cur 位置的值小于基准值，且 prev 右移一位指向的元素与cur指向的元素不同，则交换prev和cur指向的元素
- 交换基准与prev位置对应的元素
- 对基准值左右两侧的子树组重复上述步骤，直到子数组长度为0或1
代码展示：
private static int parttion(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,prev,cur);
}
cur++;
}
swap(array,prev,left);
return prev;
}快速排序也可以进行一些优化：
1、三数取中法：从数组的左端、右端、中间位置各取一个元素，选择大小为中间值的值作为基准（这样可以避免出现 “ 单分支的树 ”）
2、小规模数组改用直接插入排序：快排的递归在调用数组规模较小时（如长度小于10），递归开销会超过排序本身的成本，此时改用插入排序，可减少递归次数和时间消耗
private static void quick(int[] array, int left, int right) {
if(left>=right){
return;
}
//直接插入排序
if(right-left+1<=10){
insertSortRange(array,left,right);
return;
}
//三数取中
int index=ThreeMiddle(array,left,right);
swap(array,left,index);
int par=parttion(array,left,right);
quick(array,left,par-1);
quick(array,par+1,right);
}
private static void insertSortRange(int[] array, int left, int right) {
for (int i = left+1; i <= right; i++) {
int tmp=array[i];
int j=i-1;
for(;j>=left;j--){
if(array[j]>array[j+1]){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=tmp;
}
}
private static int ThreeMiddle(int[] array, int left, int right) {
int mid=(left+right)/2;
if(array[left]<array[right]){
if(array[left]>array[mid]){
return left;
}else if(array[right]<array[mid]){
return right;
}else {
return mid;
}
}else{
if(array[right]>array[mid]){
return right;
}else if(array[left]<array[mid]){
return left;
}else {
return mid;
}
}
}快排非递归：
- 首先我们还是需要先求出 par(左边都小于它，右边都大于它)
- 然后判断是否将其左右范围的区间入栈，如果par>left+1，说明左序列数据>1，可入栈，如果par<right-1，说明右序列数据>1，可入栈（如果它们不符合说明序列只有一个元素且已有序）
- 然后进行出栈（只要栈不为空），为新的序列范围（在出栈时要注意，栈是先进后出，所以先取出的是右范围），求新的par，再判断其左右序列是否可以入栈，重复此步骤，栈为空时，说明已有序
public static void quickNor(int[]array){
int left=0;
int right=array.length-1;
int par=parttionSpark(array,left,right);
Stack<Integer> stack=new Stack<>();
if(par>left+1){
stack.push(left);
stack.push(par-1);
}
if(par<right-1){
stack.push(par+1);
stack.push(right);
}
while(!stack.isEmpty()) {
right=stack.pop();
left=stack.pop();
par=parttionSpark(array,left,right);
if(par>left+1){
stack.push(left);
stack.push(par-1);
}
if(par<right-1){
stack.push(par+1);
stack.push(right);
}
}
}快速排序特性总结：
- 适用于大规模数据排序，实际场景中被广泛使用
- 时间复杂度：O(n*logn)，最坏情况：O(n)
- 空间复杂度:O(logn)
- 稳定性：不稳定
4、归并排序
归并排序是一种基于分治法的高效排序算法。其核心原理是将数组不断二分拆分为子数组，直到数组长度为1，再通过合并操作将两个有序子数组合并为一个更大的有序数组，最终得到完整的有序数组。
步骤：
- 将原始数组不断二分拆分，直到每个数组的长度为 1 ，停止拆分
- 从最小的有序子数组开始，两两合并为更大的有序数组。合并时通临时数组辅助，比较两个子数组的元素并按顺序放入临时数组，最终将临时数组的内容复制回原数组，重复此过程直至合并为完整的有序数组
代码展示：
public static void mergeSort(int[] array){
mergeSortChild(array,0,array.length-1);
}
private 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);
}
private static void merge(int[] array, int left, int mid, int right) {
int[] tmp=new int[right-left+1];
int k = 0;
int s1=left;
int e1=mid;
int s2=mid+1;
int e2=right;
while(s1<=e1 && s2<=e2){
if(array[s1]<array[s2]){
tmp[k++]=array[s1++];
}else {
tmp[k++]=array[s2++];
}
}
while(s1<=e1){
tmp[k++]=array[s1++];
}
while (s2<=e2){
tmp[k++]=array[s2++];
}
for (int i = 0; i < tmp.length; i++) {
array[i+left]=tmp[i];
}
}归并排序特性总结：
- 适用于处理大规模数据，尤其在外部排序（数据无法全部加载到内存）
- 时间复杂度：O(n*logn)
- 空间复杂度：O(n)
- 稳定性：稳定
三、排序算法复杂度及稳定性
| 排序方法 | 最好 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 直接插入排序 | O（n） | O(n^2) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3~1.5) | O(n^2) | O(1) | 不稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) | O(n^2) | O(1) | 稳定 |
| 快速排序 | O(n*logn) | O(n^2) | O(logn) | 不稳定 |
| 归并排序 | O(n*logn) | O(n*logn) | O(n) | 稳定 |
四、计数排序（非基于比较型（了解即可））
计数排序是一种非基于比较型排序算法，主要适用于整数或可映射为整数的有限范围数据
步骤：
- 找出待排序数组中的最大值和最小值，计算数据范围，，用于确定计数数组的长度
- 计数数组 count ，遍历待排序序列，将每个元素减去最小值为索引，对应位置的计数 加1
- 定义变量来表示结果数组 array 的位置，遍历计数数组，对于每个索引 i 下标的值不为0则执行对结果数组赋值（由于之前减去最小值，所以现在要加回去），然后 i 下标对应值--，直至遍历完成，排序完成
代码展示：
public static void countSort(int[]array){
int max=array[0];
int min=array[0];
for (int i = 1; i < array.length; i++) {
if(min>array[i]){
min=array[i];
}
if(max<array[i]){
max=array[i];
}
}
int[] count=new int[max-min+1];
for (int i = 0; i < array.length ; i++) {
int index=array[i];
count[index-min]++;
}
int j=0;
for (int i=0;i< count.length;i++) {
while(count[i]!=0){
array[j++]=i+min;
count[i]--;
}
}
}计数排序特性总结：
- 计数排序在数据范围集中时，效率很高
- 时间复杂度：O（MAX(N,范围)）
- 空间复杂度：O(范围）
- 稳定性：稳定
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
16
0- 0
已为社区贡献1条内容
所有评论(0)