写点什么

Java 实现各种内部排序算法,mysql 排它锁之行锁

作者:Java高工P7
  • 2021 年 11 月 10 日
  • 本文字数:2940 字

    阅读完需:约 10 分钟

性能:时间复杂度:最好 o(n):有序,最坏 o(n^2):逆序,平均 o(n^2);空间复杂度 o(1);稳定


public int[] straightInsertSort(int array[]){


int temp;


for(int i=1; i<array.length; i++){ //依次对 1 到 array.length-1 个元素进行处理


temp = array[i];


for(int j=0; j<i; j++){ //已排好序的 0 到 i-1 个元素


if(temp < array[j]){ //插入位置 j


for(int k=i-1;k>=j;k--){ //将 j 到 i-1 个元素向后移一个位置


array[k+1]=array[k]; //此时 array[i]为已排好序的子数组中的最大值


}


array[j] = temp; //将第 i 个元素插入到位置 j 上


break;


}


}


}


return array;


}


折半插入排序:


思想:利用折半查找的方法找出元素的待插入位置,然后再统一移动待插入位置之后的所有元素,最后将待插入元素插入到相应位置。


性能:平均情况下,比较次数 o(nlogn),移动次数 o(n^2)


时间复杂度:最好 o(n):有序,最坏 o(n^2):逆序,平均 o(n^2);空间复杂度 o(1);稳定


public int[] binaryInsertSort(int[] array){


int temp,low,high;


for(int i=1; i<array.length; i++){


temp = array[i];


//从已排好序的 0 到 i-1 个元素中,折半查找出元素的待插入位置


low = 0;


high = i-1;


while(low <= high){


if(array[(low+high)/2] <= array[i]){


low = (low+high)/2 + 1;


}else{


high = (low+high)/2 - 1;


}


}


//移动待插入位置 low 到 i-1 间的所有元素


for(int j=i-1; j>=low; j-- ){


array[j+1] = array[j];


}


array[low] = temp;


}


return array;


}


希尔排序:


思想:将排序表分割成若干个形如 L[i,i+d,i+2d,...,i+kd]的“特殊”子表,分别进行直接插入排序,当整个表中元素已呈现“基本有序”时,再对全体记录进行一次直接插入排序(d=1 时)。


步长设置:d1=array.length/2;di=di/2,最后一个增量为 1;


性能:时间复杂度:最坏 o(n^2),平均 o(n^1.3),空间复杂度 o(1),不稳定


public int[] shellSort(int[] array){


for(int d=array.length/2; d>=1; d=d/2){ //用步长值来控制循环次数


for(int i=d;i<array.length;i++){


int temp = array[i];


if(temp < array[i-d]){ //将 array[i]插入到有序增量子表中


int j;


for(j=i-d;j>=0 && temp<array[j];j-=d){


array[j+d]=array[j]; //记录后移,寻找插入位置


}


array[j+d] = temp;


}


}


}


return array;


}


冒泡排序:


思想:对于待排序表,从前往后两两比较相邻元素的值,若为逆序,则交换,直到序列比较完成。如此,每次冒泡即可得到当前待排表中的最大元素,并已放置在相应的位置。


性能:时间复杂度:最好 o(n)有序,最坏 o(n^2)逆序,平均 o(n^2),空间复杂度 o(1),稳定


public int[] bubbleSort(int[] array){


boolean flag = false; //用来标记该序列是否已是有序


for(int i=0;i<array.length-1;i++){ //做 n-1 趟冒泡


for(int j=0;j<array.length-i-1;j++){


if(array[j]>array[j+1]){


int temp = array[j];


array[j] = array[j+1];


array[j+1] = temp;


flag = true; //有元素交换,则该序列初始状况不是有序的


}


}


if(flag == false){ //本趟遍历后没有发生交换,说明表已经有序


return array;


}


}


return array;


}


快速排序:


思想:基于分治的思想:在待排序表中任取一个元素 pivot 作为基准,通过一趟排序将待排序表划分为独立的两部分,使得一部分中所有元素小于等于 pivot,另一部分中所有元素大于 pivot,则 pivot 放在了其最终位置上,这个过程称为一趟快速排序。而后递归地对两个子表重复上述过程,直到每部分内只有一个元素或空为止。


性能:?空间复杂度:需要递归工作栈:最坏 o(n),平均 o(logn)


时间复杂度:最坏:o(n^2)初始表基本有序或基本逆序,平均 o(n*logn)


不稳定


public int[] quickSort(int[] array,int low,int high){


if(low<high){ //递归跳出的条件


int mid= partition(array, low, high); //划分,得到枢值所在的下表


quickSort(array,low,mid-1); //依次对两个子表进行递归排序


quickSort(array,mid+1,high);


}


return array;


}


//快速排序的划分函数


public int partition(int[] array,int low, int high){


int pivot = array[low]; //每次取数组中的第一个元素为基准


while(low < high){ //跳出循环的条件


while(low<high && array[high] > pivot){ //从右边开始找到第一个小于或等于 pivot 的值


high--;


}


while(low<high && array[low] < pivot){ //从左边开始找到第一个大于或等于 p


《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开:qq.cn.hn/FTe 免费领取
复制代码


ivot 的值


low++;


}


int temp = array[low]; //交换


array[low] = array[high];


array[high] = temp;


if(low<high && array[low] == pivot && array[high] == pivot){ //特殊情况


low++;


}


}


return low;


}


简单选择排序:


思想:假设排序表 array[0,...,n-1],第 i 趟排序即从 array[0,...,n-1]中选择关键字最小的元素与 array[i]交换,每一趟排序可以确定一个元素的最终位置,这样经过 n-1 趟派克就可以使整个序列有序。


性能:时间复杂度:o(n^2),空间复杂度 o(1),不稳定


public int[] simpleSelectSort(int[] array){


for(int i=0;i<array.length -1;i++){ //一共进行 n-1 趟


int min = i; //记录最小元素位置


for(int j=i+1;j<array.length;j++){ //在 array[i,...,n-1]中选择最小的元素


if(array[j] < array[min]){


min = j; //更新最小元素的位置


}


}


int temp = array[i]; //将最小元素与第 i 个位置交换


array[i] = array[min];


array[min] = temp;


}


return array;


}


堆排序:Java实现堆排序(大根堆)


归并排序:


思想:“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假设待排序表含有 n 个记录,则可以看成是 n 个有序的子表,每个子表的长度为 1,然后两两归并,得到(n/2)个长度为 2 或 1 的有序表;再两两归并,...,如此重复,直到合并成一个长度为 n 的有序表为止,这种排序方法称为 2-路归并排序。


递归形式的 2-路归并排序算法是基于分治的,其过程如下:


分解:将含有 n 个元素的待排序表分成各含有 n/2 个元素的子表,采用 2-路归并排序算法对两个子表递归地进行排序;


合并:合并两个已排序的子表得到排序结果。


性能:空间复杂度:o(n);时间复杂度:o(nlogn);稳定


public int[] mergeSort(int[] array,int low, int high){


if(low < high){ //递归结束的条件


int mid = (low + high)/2; //二路归并排序,从中间划分两个子序列【分解过程】


mergeSort(array, low, mid); //对左侧子序列进行递归排序


mergeSort(array, mid+1, high); //对右侧子序列进行递归排序


merge(array,low,mid,high); //归并【合并过程】


}


return array;


}


//将前后相邻的两个有序表归并为一个有序表


private void merge(int[] array,int low, int mid, int high){


int[] tempArray = new int[array.length]; //辅助数组 tempArray


for(int i=low;i<=high;i++){ //将 array 数组中[low...high]的元素复制到辅助数组 tempArray 中


tempArray[i] = array[i];


}


int i,j,k;


for(i=low,j=mid+1,k=i;i<=mid && j<=high;k++){


if(tempArray[i]>tempArray[j]){ //比较 tempArray 的左右两端中的元素


array[k] = tempArray[j++]; //将较小值复制到 array 中


}else{


array[k] = tempArray[i++];


}


}


while(i<=mid){ //若第一个表未检测完,复制


array[k++] = tempArray[i++];


}


while(j<=high){ //若第二个表未检测完,复制


array[k++] = tempArray[j++];


}


}


按 Ctrl+C 复制代码

用户头像

Java高工P7

关注

还未添加个人签名 2021.11.08 加入

还未添加个人简介

评论

发布
暂无评论
Java实现各种内部排序算法,mysql排它锁之行锁