更新时间:2020-06-23 12:50:06 来源:极悦 浏览1760次
排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序!
1.排序
(1)冒泡排序
重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。时间复杂度O(n2),为稳定算法。
将数依次进行比较,并将大(或小)的,网后放,如下:
public static void bubbleSort(int[]arr){
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
//-1为了防止溢出
if(arr[j]>arr[j+1]){
//把大的数放在后面
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
(2)快速排序
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
public static void quickSort(int[]numbers,int low,int high){
if(low<high){
int middle=getMiddle(numbers,low,high);
//将numbers数组进行一分为二
quickSort(numbers,low,middle-1);
//对低字段表进行递归排序
quickSort(numbers,middle+1,high);
//对高字段表进行递归排序
}
}
(3)选择排序
每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5,5,3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。
public static void selectSort(int[]a){
int minIndex=0;
int temp=0;
for(int i=0;i<a.length-1;i++){
minIndex=i;
//无序区的最小数据数组下标
for(intj=i+1;j<a.length;j++){
//在无序区中找到最小数据并保存其数组下标
if(a[j]<a[minIndex]){
minIndex=j;
}
}
//将最小元素放到本次循环的前端
temp=a;
a=a[minIndex];
a[minIndex]=temp;
}
}
(4)插入排序
每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
每一个数和它前面的数依次进行比较,因为前面的数的顺序是已经排好的
private static int[]insertSort(int[]arr){
for(int i=1;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
break;
}
}
}
return arr;
}
(5)希尔排序
把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
public static void main(String[]args)
{
int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
//希尔排序
int d=a.length;
while(true){
d=d/2;
for(int x=0;x<d;x++){
for(int i=x+d;i<a.length;i=i+d){
int temp=a;
int j;
for(j=i-d;j>=0&&a[j]>temp;j=j-d){
a[j+d]=a[j];
}
a[j+d]=temp;
}
}
if(d==10){
break;
}
}
}
(6)归并排序
建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。时间复杂度O(n log n)。
public static int[]sort(int[]nums,int low,int high){
int mid=(low+high)/2;
if(low<high){
//左边
sort(nums,low,mid);
//右边
sort(nums,mid+1,high);
//左右归并
merge(nums,low,mid,high);
}
return nums;
}
以上就是极悦java培训机构的小编针对“编程技术分享之Java简单算法的学习”的内容进行的回答,希望对大家有所帮助,如有疑问,请在线咨询,有专业老师随时为你服务。
0基础 0学费 15天面授
Java就业班有基础 直达就业
业余时间 高薪转行
Java在职加薪班工作1~3年,加薪神器
工作3~5年,晋升架构
提交申请后,顾问老师会电话与您沟通安排学习