基本排序算法
排序算法:
快速排序:
时间复杂度O(nlogn) 空间复杂度1
适用于大多数排序,性能很高
不稳定排序
步骤描述:
取数组首元素为基准值。设置一个i指针指向首元素,再设置一个j指针指向尾元素。在i<j的前提下。从j开始往回找,遇到第一个比基准值小的数,将该元素与基准值交换,i++;再从i往后找,遇到第一个比基准值大的值,使它与基准值交换,j++;直到i>=j停止。
代码:
int length=array.length;
public void sort(int[] array,int begin,int end){
int i=begin;
int j=end;
int base=array[begin];
While(i<j){
Int temp;
While(i<j&&array[j]>base){
j--;
}
if(i<j){
temp=array[j]
array[i]=array[j];
array[j]=temp;
i++;
}
While(i<j&&array[i]<base){
i++;
}
If(i<j){
temp=array[i];
array[i]=array[j];
array[j]=temp;
j--;
}
}
array[i]=base;
sort(array,begin,i-1);
Sort(array,i+1,end);
}
插入排序:
时间复杂度O(n^2); 空间复杂度1
使用场景:近乎有序,向序列中插入
稳定
步骤描述:
将数组分成一份有序的数组,一份待排序的数组(如果从零排序把第一个数当做有序数组)将待排序的数组从第一个元素开始,依次与有序的数组最后一个元素作比较,如果大于它不变,如果小于前一个元素就触发一个循环:将该元素拿出来,与有序数组的从后到前的每一个值作比较,当发现比前一个小就把前一个数组后移一位,直到找到合适的位置插进去,或者比所有元素小插到第一个位置。
代码实现:
Int length=array.length;
Public void sort(){
for(int i=1;i<length;i++){
if(array[i]>array[i-1]){
int temp=array[i];
for(int j=i;j>0;j--){
If(temp<array[j-1]){
array[j]=array[j-1];
}else{
array[j]=temp;
}
}
}
}
}
冒泡排序:
时间复杂度O(n^2);空间复杂度1
稳定
步骤描述:
冒泡,从第一个元素开始,两个两个作比较,如果前一个大于后一个就交换。
大循环(n-1次)每次循环能找出一个当前序列里最大的;
小循环(n-1次)每次两两比较,共比较n-1次
代码实现:
public void sort(){
Int length=array.length;
for(int i=0;i<length-1;i++){
for(int j=0;j<length-1;j++){
if(array[j]>array[j+1]){
int temp=array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}
}
相关推荐
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。