基本排序算法

排序算法:

快速排序:

时间复杂度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;

}

}

}

}

相关推荐