各种常用排序算法分析

各种常用排序算法分析

 

一、选择排序

很简单就是依次从要排序的数据中选择最小(大)的，第二小(大)的.........

看代码:

  /**

 * 选择排序;

 * @param array

 * @param left

 * @param right

 */

public static void selectSort(int[] array,int left,int right){

for(int i=0;i<right-left+1;i++){

selectMin(array,left+i,right);

}

}



   /**

 * 选择最小的元素--将数组中的元素移动到第一位;

 * @param array

 * @param left

 * @param right

 * @return

 */

public static void selectMin(int[] array,int left,int right){



if(left==right){//只有一个元素;

return;

}else{

for(int i=left+1;i<right;i++){

if(array[i]<array[left]){

//交换元素;

int temp=0;

temp=array[i];

array[i]=array[left];

    array[left]=temp;

}

}

}



}

 

 

 分析一下算法的复杂度:时间O(n2)，空间O(1);

 

二、直接插入排序

我觉得这种排序特别适合链表这种在逻辑上连续在物理上不连续的数据结构，否则需要反复的移动数据;

直接插入排序就是将要插入的元素插入已经排好序的顺序表中，使得插入以后的顺序表任然有序;

代码：

 /**

 * 插入排序;

 * @param array

 * @param left

 * @param right

 */

public static void insertSort(int[] array,int left,int right){



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

arrayAdjust(array,0,i);

}



}



/**

 * 将数组调整--认为数组前n-1个元素是有序的最后一个元素待插入;

 * @param array

 * @param low

 * @param high

 */

public static void arrayAdjust(int[] array,int low,int high){

int e=array[high];

for(int i=low;i<high;i++){

if(e<array[i]){

//移动元素并插入;

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

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

}

//赋值;

array[i]=e;

break;

}

}

}

 

 

  很明显在链表中可以省去移动数据的操作，显得简单了许多。

算法复杂度分析：O(n2);

 

 

三、归并排序

归并排序就是将两个已经排好序的序列合并成一个有序的序列;

 代码：

/**

 * 归并排序;

 * 

 * @param a

 * @param left

 * @param right

 */

public static void mergeSort(int[] a, int left, int right) {



if (right > left) {



// 取得中间值;

int mid = (left + right) / 2;

// 左归并;

mergeSort(a, left, mid);

// 右归并;

mergeSort(a, mid + 1, right);

// 排序之后再归并;

merge(a, left, mid, right);



}



}

/**

 * 归并;

 * 

 * @param array

 * @param low

 * @param mid

 * @param high

 */

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



// 开辟两个数组;

int[] a = new int[mid - low + 1];// 左边数组;

int[] b = new int[high - mid];// 右边数组;



int i, j;

// 拷贝元素;

for (i = 0; i < a.length; i++) {

a[i] = array[i + low];

}

for (j = 0; j < b.length; j++) {

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

}



i = j = 0;

int k = 0;

// 归并;

while (i < a.length && j < b.length) {

if (a[i] < b[j]) {

array[low+k++] = a[i++];

} else {

array[low+k++] = b[j++];

}

}



// 剩余拷贝;

if (i < a.length) {

for (; i < a.length; i++) {

array[low+k++] = a[i];

}

} else {

for (; j < b.length; j++) {

array[low+k++] = b[j];

}

}



}

 

 

   归并排序是一种比较稳定的排序，但是它有一个不好的地方是在归并的时候必须要开辟新的空间来存储数据，所以它的空间复杂度较高，对于内存要求较高的程序来说不推荐使用归并排序。

算法复杂度分析：O(nlogn);

四、快速排序

效率很高的排序方式啊，ACM强烈推荐

/**

 * 快速排序;

 * @param array

 * @param low

 * @param high

 */

public static void quickSort(int[] array,int left,int right){



if(left<right){



int flag=partition(array, left, right);

//递归调用快速排序算法;

quickSort(array,left,flag-1);

quickSort(array,flag+1,right);



}



}



/**

 * 调整数组;

 * @param array

 * @param low

 * @param high

 * @return

 */

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



//取得标志;

int pivot=array[low];

int temp=0;//临时变量;



while(low<high){



while(low<high&&array[high]>=pivot){

high--;

}



//交换;

temp=array[high];

array[high]=array[low];

array[low]=temp;

while(low<high&&array[low]<=pivot){

low++;

}



//交换;

temp=array[high];

array[high]=array[low];

array[low]=temp;

}



return low;



}

 

 

平均效率较高是O(nlogn),不好的地方是它是一种不稳定的排序方式，如果每次划分的元素是有一边只有一个，那么就没有得到很好的划分，所以此时运行时间较高。较好的情况是每次划分都比较均衡，复杂度能达到nlogn；

五、堆排序

堆排序虽然有的时候效率没有快速排序那么高，但是它是一种稳定的排序 ，排序实现利用大根堆(小跟堆)的性质来完成排序，将数组看成一个完全二叉树，然后我们在排序的时候要反复的来建堆。取得堆顶元素，调整到堆的末尾。

代码：

/**

 * 堆排序算法;

 * @param array

 * @param length

 */

public static void heapSort(int[] array,int length){



//先建堆将第一个元素调整为最大的元素;

for(int i=length/2-1;i>=0;i--){

maxHeapfy(array,i,length);

}



    int temp=0;

//堆排序;

//反复建堆;

for(int i=length-1;i>0;i--){

//堆顶先和堆的最后一个元素交换;

temp=array[0];

array[0]=array[i];

array[i]=temp;

//在将0-i调整为一个大根堆;

maxHeapfy(array,0,i);

}



}



/**

 * 将堆调整为大根堆--以pos为堆顶;

 * @param array

 * @param pos--起始位置;

 * @param len--数组的长度;

 */

public static void maxHeapfy(int[] array,int pos,int len){



//节点孩子的位置

int left=2*pos;

int right=2*pos+1;



int largest=0,temp;

//取得最大元素的位置;

if(left<len&&array[left]>array[pos]){

largest=left;

}

if(right<len&&array[right]>array[largest]){

largest=right;

}else{

largest=pos;

}



if(largest!=pos){//不相等交换堆顶元素;

temp=array[largest];

array[largest]=array[pos];

array[pos]=temp;



//递归调用;

maxHeapfy(array,largest,len);



}



}

 

 

各种排序还有很多种应用，今晚累了，且听下回分解！

<!--EndFragment-->