Java:数据结构-排序
排序
排序的概念:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
常见排序算法的实现
1.直接插入排序
性质:
- 元素集合越接近有序,直接插入排序算法的时间效率越高
- 时间复杂度:O(N^2)
- 空间复杂度:O(1),它是一种稳定的排序算法
- 稳定性:稳定
public static void insetSort(int[] array){
for (int i = 0; i <array.length; i++) {
int tem=array[i];
int j = i-1;
for (; j>0 ; j--) {
if(array[j]>tem){
array[j+1]=array[j];
}else {
array[j+1]=tem;
break;
}
}
array[j+1]=tem;
}
}
2. 希尔排序
性质:
稳定性:不稳定的
时间复杂度:n^1.3 - n^1.5
空间复杂度:O(1)
public void shallSort(int[] array,int gap){
gap=array.length;
while (gap>1){
gap/=2;
shall(array,gap);
}
}
public static void shall(int[] array,int gap){
for (int i = gap; i <array.length; i++) {
int tem=array[i];
int j = i-gap;
for (; j>0 ; j-=gap) {
if(array[j]>tem){
array[j+gap]=array[j];
}else {
array[j+gap]=tem;
break;
}
}
array[j+gap]=tem;
}
}
3. 选择排序
性质:
时间复杂度:O(N^2)
和数据 是否有序无关
空间复杂度:O(1)
稳定性:不稳定的排序
public void selectSort(int[] array){
for (int i = 0; i < array.length; i++) {
int num=i;
int j =i-1;
for (; j <array.length ; j++) {
if(array[j]<array[num]){
num=j;
}
}
swap(array,i,j);
}
}
public static void swap(int[] array, int i, int j){
int tem=array[i];
array[i]=array[j];
array[j]=tem;
}
优化为(同时找最大值和最小值)
public static void swap(int[] array, int i, int j){
int tem=array[i];
array[i]=array[j];
array[j]=tem;
}
public void selectSort1(int[] array){
int left=0;
int right=array.length;
while (left<right) {
int min=left;
int max=left;
for (int i = left + 1; i <=right; i++) {
if(array[i]>array[max]){
max=i;
}
if(array[i]<min){
min=i;
}
}
swap(array,left,min);
if (left==max){
max=min;
}
swap(array,right,max);
left++;
right--;
}
}
4.堆排序
时间复杂度:O(n*logN)
空间复杂度:O(1)
稳定性:不稳定
heapSort(int[] array)方法的作用:主方法,执行堆排序的整体流程
createHeap(int[] array)方法的作用:将输入数组构建成一个最大堆
siftDown(int[] array, int parent, int length)方法的作用:在堆中调整节点,以维持最大堆的性质。
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 parent=(array.length-1-1)/2;parent>=0;parent--){
siftDown(array,parent, array.length);
}
}
public static void siftDown(int[] array,int parent,int length){
int child=parent*2+1;
while (child<length){
if (child+1<length && array[child]<array[child+1]){
child++;
}
if (array[child]>array[parent]){
swap(array,child,parent);
parent=child;
child=2*parent+1;
}else {
break;
}
}
}
5.冒泡排序
时间复杂度:讨论 没有优化的情况下,也就是 没有下方的boolean元素和-i操作168 * O(N^2)
空间复杂度:O(1)
稳定性:稳定的排序
如果有1000个数,得判断999次,但是有可能5次就排好序了,为了防止排好序还继续判断,所以我们优化了一下代码,如果不进入循环,那么我们判断已经排好序了,可以直接break。
public static void bubbleSort(int[] array){
boolean flg=false;
for (int i=0;i<array.length;i++){
for (int j = 0; j < array.length-1-i; j++) {
if(array[j]>array[j+1]){
swap(array,j,j+1);
flg=true;
}
}
if(!flg){
break;
}
}
}
6.快速排序
时间复杂度:
最坏情况:当数据给定的是1 2 3 4 5 6 7.....有序的情况下 确实是O(n^2) 9 8 7 6 5 4
最好情况:O(N*logN)
空间复杂度:
最坏情况:O(N)
最好情况:O(logN)
稳定性:不稳定性
1.Hoare版
public void quickSort(int[] array){
quick(array,0,array.length-1);
}
private void quick(int[] array,int start,int end){
if(start>end){
return;
}
int mid=partition(array,start,end);
quick(array,start,mid-1);
quick(array,mid+1,end);
}
private int partition(int[] array, int left, int right) {
int key=array[left];
int ketPotion=left;
while (left<right){
while (left<right && array[right]>=key){
right--;
}
while (left<right && array[left]<=key){
left++;
}
swap(array,left,right);
}
swap(array,ketPotion,left);
return left;
}
注:
1.为什么从后往前找,而不是从前往后找呢?
如果从前往后,则会出现这种情况
2.为什么这里会有等号
如果没有等号,就会出现死循环的情况。
2.挖坑法
private int partition1(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;
}
3.前后指针法
private int partition2(int[] array,int left,int right){
int cur=left+1;
int prev=left;
while (cur<=right){
if(array[cur]<array[left] && array[prev++]!=array[cur]){
swap(array,prev,cur);
}
cur++;
}
swap(array,left,prev);
return prev;
}
快速排序的优化:
1.三数取中法(找mid)
因为一组数据如果正好是顺序的,会使快排的时间复杂度为O(n2),三数取中法选取的枢轴更接近数组的中位数,从而更有可能将数组划分为两部分,使得递归树更加平衡,提高整体效率,通过三数取中法,快速排序的平均时间复杂度更接近 O(nlogn)。
private void quick(int[] array,int start,int end){
if(start>end){
return;
}
int midIndex=getMidNumber(array,start,end);
swap(array,start,midIndex);
int mid=partition(array,start,end);
quick(array,start,mid-1);
quick(array,mid+1,end);
}
private int getMidNumber(int[] array,int start,int end){
int mid=(start+end)/2;
if(array[start]>array[end]){
if(array[end]>array[mid]){
return end;
}else if (array[mid]>array[start]){
return start;
}else {
return mid;
}
}else {
if(array[start]>array[mid]){
return start;
}else if(array[mid]>array[end]){
return end;
}else {
return mid;
}
}
}
2.在接近有序时,使用快速排序(在一定的小区间)
public void quickSort(int[] array){
quick(array,0,array.length-1);
}
private void quick(int[] array,int start,int end){
if(start>end){
return;
}
if(end-start+1<=10){
insetSortRange(array,start,end);
return;
}
int midIndex=getMidNumber(array,start,end);
swap(array,start,midIndex);
int mid=partition(array,start,end);
quick(array,start,mid-1);
quick(array,mid+1,end);
}
private int getMidNumber(int[] array,int start,int end){
int mid=(start+end)/2;
if(array[start]>array[end]){
if(array[end]>array[mid]){
return end;
}else if (array[mid]>array[start]){
return start;
}else {
return mid;
}
}else {
if(array[start]>array[mid]){
return start;
}else if(array[mid]>array[end]){
return end;
}else {
return mid;
}
}
}
public static void insetSortRange(int[] array,int start,int end){
for (int i = start+1; i <end; i++) {
int tem=array[i];
int j = i-1;
for (; j>0 ; j--) {
if(array[j]>tem){
array[j+1]=array[j];
}else {
array[j+1]=tem;
break;
}
}
array[j+1]=tem;
}
}
快排的非递归形式:
利用栈来做,通过使用栈来模拟递归过程,处理当前范围的数组,并将分区后的左右子数组的范围压入栈中,直到所有范围都处理完毕,每次调用 partition
方法都会把数组根据基准值分成两部分,确保左侧部分的所有元素都小于基准值,右侧部分的所有元素都大于基准值。这样,基准值最终会处于其正确的位置上。
public void quickSortNor(int[] array,int start,int end){
if(array.length<=0){
return;
}
int pilot=partition(array,start,end);
Stack<Integer> stack=new Stack<>();
if(start+1<pilot){
stack.push(start);
stack.push(pilot-1);
}
if (end-1>pilot){
stack.push(pilot+1);
stack.push(end);
}
while (stack.isEmpty()){
start=stack.pop();
end=stack.pop();
pilot=partition(array,start,end);
if(start+1<pilot){
stack.push(start);
stack.push(pilot-1);
}
if (end-1>pilot){
stack.push(pilot+1);
stack.push(end);
}
}
}
private int partition(int[] array, int left, int right) {
int key=array[left];
int ketPotion=left;
while (left<right){
while (left<right && array[right]>=key){
right--;
}
while (left<right && array[left]<=key){
left++;
}
swap(array,left,right);
}
swap(array,ketPotion,left);
return left;
}
7.归并排序
拆分:
合并:
public void mergeSort(int[] array){
message(array,0,array.length-1);
}
public void message(int[] array,int left,int right){
//拆分
if(left>=right){
return;
}
int mid=(left+right)/2;
message(array,left,mid);
message(array,mid+1,right);
//合并
merge(array,left,right,mid);
}
private void merge(int[] array, int left, int right,int mid) {
int[] tem=new int[10];
int k=0;
int s1=left;
int s2=mid+1;
while (s1<=mid && s2<=right){
if (array[s1]<=array[s2]){
//tem[k++]=array[s1++];
tem[k]=array[s1];
k++;
s1++;
}else {
//tem[k++]=array[s2++];
tem[k]=array[s2];
k++;
s2++;
}
}
while (s1<=mid){
tem[k++]=array[s1++];
}
while (s2<=mid){
tem[k++]=array[s2++];
}
for (int i = 0; i < k; i++) {
array[i+left]=tem[i];
}
}
归并排序的非递归形式:
public void messageNorSort(int[] array){
int gap=1;
while (gap<=array.length-1){
for (int i = 0; i <array.length ; i=i+gap*2) {
int left=i;
int mid=left+gap-1;
if(mid>=array.length){
mid=array.length-1;
}
int right=mid+gap;
if(right>=array.length){
right=array.length-1;
}
merge(array,left,right,mid);
}
gap*=2;
}
}
private void merge(int[] array, int left, int right,int mid) {
int[] tem=new int[10];
int k=0;
int s1=left;
int s2=mid+1;
while (s1<=mid && s2<=right){
if (array[s1]<=array[s2]){
//tem[k++]=array[s1++];
tem[k]=array[s1];
k++;
s1++;
}else {
//tem[k++]=array[s2++];
tem[k]=array[s2];
k++;
s2++;
}
}
while (s1<=mid){
tem[k++]=array[s1++];
}
while (s2<=mid){
tem[k++]=array[s2++];
}
for (int i = 0; i < k; i++) {
array[i+left]=tem[i];
}
}
8.其他排序
1.计数排序:
public void countSort(int[] array){
//找出最大值和最小值
int maxVal=array[0];
int minVal=array[0];
for (int i = 0; i < array.length; i++) {
if(array[i]>maxVal){
maxVal=array[i];
}
if(array[i]<minVal){
minVal=array[i];
}
}
int len=maxVal=minVal+1;
int[] count=new int[len];
for (int i = 0; i < array.length; i++) {
int index=array[i];
count[index+minVal]++;
}
int index=0;
for (int i = 0; i < count.length; i++) {
while (count[i]!=0){
array[index]=count[i+minVal];
index++;
count[i]--;
}
}
}
2.基数排序
3.桶排序
希望能对大家有所帮助!!!!