基于比较的排序算法

一、选择排序

 

思路：将总的array分成两个部分，一部分是已经排好序的subarray1，另一部分是待排序的subarray2，每次都从subarray2中选择最小的加入到subarray1中，直至所有的元素加入到subarray1中。

 

实现：

 

Void swap(int *xp,int *yp)

{

Int t=*xp;

*xp=*yp;

*yp=t;

}

 

Void selecttionSort(int arr[],int n)

{

Int i,j,minIndex;

For(i=0;i<n-1;i++)

{

minIndex=i;

For(j=i+1;j<n;j++)

{

If(arr[j]<arr[minIndex])

{

minIndex=j;

}

}

Swap(&arr[i],arr[minIndex]);

}

}

 

时间复杂度：O(n*n)

 

二、冒泡排序

 

思路：将总的array分成两个部分，一部分是已经排好序的subarray2，另一部分是待排序的subarray1，每次都比较临近的两个元素，将较小的的元素置于较大元素之前。遍历一轮之后可找到最大的元素以交换置subarray1末尾，将subarray1中的最后元素归入subarray2中

 

实现：

 

Void swap(int *xp,int *yp)

{

Int t=*xp;

*xp=*yp;

*yp=t;

}

 

void bubbleSort(int arr[],int n)

{

int i,j;

for(i=0;i<n-1;i++)

{

for(j=1;j<n-i;j++)

{

if(arr[j]<arr[j-1])

{

swap(&arr[j],&arr[j-1]);

}

}

}

}

 

时间复杂度：O(n*n)

但是上面的算法存在一些缺陷，就是当input的是一个有序的array时，依然需要O（n*n）的时间，我们可以改进使得当input的是一个有序array时，时间复杂度为O(n).

 

改进之后：

 

void bubbleSort(int arr[],int n)

{

int i,j;

bool swapped; /*增加一个判断是否进行交换的变量，如果遍历一遍依然没有进行交换，说明array是有序的*/

for(i=0;i<n-1;i++)

{

swapped=false;

for(j=1;j<n-i;j++)

{

if(arr[j]<arr[j-1])

{

swap(&arr[j],&arr[j-1]);

swapped=true;

}

}

if(swapped==false)

{

break;

}

}

}

 

 

 

三、插入排序

 

思路：将总的array分成两个部分，一部分是已经排好序的subarray1，另一部分是待排序的subarray2。每次都取出subarray2中的第一个元素，将其插入到subarray1中正确的位置，使得subarray1有序。

 

 

实现：

 

void insertionSort(int arr[],int n)

{

int i,j,key;

for(i=1;i<n;i++)

{

key=arr[i];

j=i-1;

while(j>=0&&arr[j]>key)

{

arr[j+1]=arr[j];

j--;

}

arr[j+1]=key;

}

}

 

时间复杂度：O(n*n)

 

四、归并排序

 

思路：运用分而治之的思想，将大规模的array分解成许多小规模的subarray，将小规模的subarray排成有序之后再组装成有序的array。

 

实现：

 

void merge(int arr[],int l,int m,int r)

{

int i,j,k;

int n1=m-l+1;

int n2=r-m;

int L[n1+1],R[n2+1];

for(int i=0;i<n1;i++)

{

L[i]=arr[l+i];

}

for(j=0;j<n2;j++)

{

R[j]=arr[m+1+j];

}

L[i]=INT_MAX;

R[j]=INT_MAX;

i=0;

j=0;

for(k=l;k<=r;k++)

{

if(L[i]<R[j])

{

arr[k]=L[i];

i++;

}else

{

arr[k]=R[j];

j++;

}

}

}

 

void mergeSort(int arr[],int l,int r)

{

if(l<r)

{

int m=(l+r)/2;

mergeSort(arr,l,m);

mergeSort(arr,m+1,r);

merge(arr,l,m,r);

}

}

 

时间复杂度：O(nLogn)

 

 

五、堆排序

思路： 1.建堆，升序为大顶堆，降序为小顶堆

2.交换堆顶元素与最后一个元素

3.堆的规模减1

4.维持大顶堆的性质

5.重复2，3，4直到堆的规模为1

 

实现：

 

void heapify(int arr[],int n,int i)

{

int largest=i;

int l=2*i+1;

int r=2*i+2;

if(l<n&&arr[l]>arr[largest])

{

largest=l;

}

if(r<n&&arr[r]>arr[largest])

{

largest=r;

}

if(largest!=i)

{

swap(&arr[largest],&arr[i]);

heapify(arr,n,largest);

}

}

 

void heapSort(int arr[],int n)

{

int i;

//建堆

for(i=n/2-1;i>=0;i--)

{

heapify(arr,n,i);

}

//交换

for(i=n-1;i>0;i--)

{

swap(&arr[0],&arr[i]);

heapify(arr,i,0);//维持堆的性质

}

}

 

 

时间复杂度：O(nLogn)

 

六、快速排序

 

思路：

与mergeSort一样，都运用了分而治之的思想。不同的是quickSort将array分成三部分：中间元素pivot，比pivot都小的subarray1,和比pivot都大的subarray2.

 

实现：

 

int partition(int arr[],int l,int r)

{

int pivot=arr[r];

int i=l-1;

int j;

for(j=l;j<r;j++)

{

if(arr[j]<pivot)

{

i++;

swap(&arr[j],&arr[i]);

}

}

swap(&arr[i+1],&arr[r]);

return i+1;

}

 

void quickSort(int arr[],int l,int r)

{

if(l<r)

{

int pi=partition(arr,l,r);

quickSort(arr,l,pi-1);

quickSort(arr,pi+1,r);

}

}

 

时间复杂度：

Average Case : O(nLogn)

Worst Case : O(n*n)

 

而为了最大程度的避开Worst Case，我们可以采用随机版本的quickSort

 

 

int randomNum(int l,int r)

{

    srand((unsigned int)time(NULL));

    return rand()%(r-l+1)+l;

}

int randomizedPartition(int arr[],int l,int r)

{

int ran=randomNum(l,r);

swap(&arr[ran],&arr[r]);

return partition(arr,l,r);

}

void randomizedQuickSort(int arr[],int l,int r)

{

if(l<r)

{

int pi=randomizedPartition(arr,l,r);

randomizedQuickSort(arr,l,pi-1);

randomizedQuickSort(arr,pi+1,r);

}

}

<!--EndFragment-->