几种常见排序算法及实现

1.冒泡排序（Bubble Sort）

相邻两个元素作比较，冒泡排序是稳定的。算法时间复杂度是O(n^2)。
基本思想：
1）第一轮比较，找出最大的元素；第二轮找出次大的元素……

2）若有N个元素进行排序，一共比较N-1轮，第M轮要进行N-M次比较；

3）代码实现：
  static void BubbleSort(int[] arr){
for (int times=1,times<=arr.length-1,times++)  //比较arr.length-1轮
{
  for (int i=1,i<=arr.length-times,i++)  //每一轮比较arr.length-times次
  {
if (arr[i-1]>arr[i]){
temp=arr[i-1]
arr[i-1]=arr[i] 
arr[i]=temp
}
  }
}
  }

2.选择排序（Select Sort）

用某一位置的元素依次与其它位置元素相比较。直接选择排序是不稳定的，算法平均时间复杂度是O(n^2)。
基本思想：
（1）第一轮比较完毕，出现最小值，第二轮比较完毕，出现次小值……

（2）与冒泡算法一样，若有N个元素进行排序，一共比较N-1轮，第M轮要进行N-M次比较,但是每一轮只交换一次数值

（3）代码实现：

static void SelectSort(int[] arr){
for (int times=0,times<=arr.length-1,times++)  //以索引为0的元素作为第一个元素，依次与其它元素进行比较。
{
  int minindex=times
  for (int i=times+1,i<=arr.length,i++)  //i代表索引为i的被比较元素，可以取到arr.length。
  {
if (arr[i]<arr[minindex]){
minindex=i }
  }
  temp=arr[times]
  arr[times]=arr[minindex] 
  arr[minindex]=temp
}
  }

3.快速排序

快速排序是对冒泡排序的一种改进。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
基本思想：
（1）首先任意选择一个元素作为初始元素key（一般取第一个元素）

（2）从两端开始分别找：从右往左，寻找比key值小的元素交换位置；再从左往右，寻找比key值大的元素交换位置；

（3）如此依次循环步骤1.2

(4)代码实现：

void quicksort(int left,int right)  
{  
if(left>right) return ;  
else  
{  
int i=left;  
int j=right;  
T t;  
T temp=data[left];  
while(i!=j)  
{  
while(i<j&&data[j]>=temp) j--;  //记住必须先动j   
while(i<j&&data[i]<=temp) i++;  
if(i!=j) swap(i,j);  //原地交换   
}  
swap(left,i);  
quicksort(left,i-1);  
quicksort(i+1,right);   
}  
}

4.堆排序

堆排序是一种树形选择排序。
堆排序的时间复杂度为O(n*log(n))，非稳定排序，原地排序(空间复杂度O(1))。

基本思想：分为最大化堆和最小化堆。

第1趟将索引0至n-1处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的最后一个节点交换，就使的这组数据中最大(最小)值排在了最后。

第2趟将索引0至n-2处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第二个节点交换，就使的这组数据中最大(最小)值排在了倒数第2位。

…

第k趟将索引0至n-k处的全部数据建大顶(或小顶)堆，就可以选出这组数据的最大值(或最小值)。将该堆的根节点与这组数据的倒数第k个节点交换，就使的这组数据中最大(最小)值排在了倒数第k位。

代码实现

#include<memory.h>
#include<stdio.h>
#include<stdlib.h>
void swap(void* x, void* y, size_t sz) {
void* t = malloc(sz);
memcpy(t, x, sz);
memcpy(x, y, sz);
memcpy(y, t, sz);
free(t);
}
void makeHeap(void* x, int i, int n, size_t sz, int(*cmp)(const void*, const void*)) {
char* y = (char*)x;
int l = 2 * i + 1;
int r = 2 * i + 2;
int m;
if (l<n && (*cmp)(y + l*sz, y + i*sz)>0) m = l;
else m = i;
if (r<n && (*cmp)(y + r*sz, y + m*sz)>0) m = r;
if (m != i){
swap(y + i*sz, y + m*sz, sz);
makeHeap(x, m, n, sz, cmp);
}
}
void buildHeap(void* x, int n, size_t sz, int(*cmp)(const void*, const void*)) {
for (int i = n / 2 - 1; i >= 0; i--) makeHeap(x, i, n, sz, cmp);
}
void heapSort(void* x, int n, size_t sz, int(*cmp)(const void*, const void*)) {
buildHeap(x, n, sz, cmp);
char* y = (char*)x;
for (int i = n - 1; i >= 1; i--){
swap(y, y + i*sz, sz);
makeHeap(x, 0, --n, sz, cmp);
}
}

void p(int* x,int n){
for (int k = 0; k < n; k++){
printf("%d ", x[k]);
}
printf("\n");
}

int less(const void* a, const void* b){
return *((int*)a) < *((int*)b);
}
int greater(const void* a, const void* b){
return *((int*)a) *((int*)b);
}
int main(){
int x[] = { 2, 3, 4, 6, 8, 2, 9, 0 };
// 降序全排列
heapSort(x, 8, sizeof(int), less);
p(x, 8);
// 升序全排列
heapSort(x, 8, sizeof(int), greater);
p(x, 8);
// 最大的4个元素，在数组末尾
heapSort(x, 4, sizeof(int), less);
p(x, 8);
}

5.归并排序

是建立在归并操作上的一种有效的排序算法。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法时间复杂度可以达到O(n)

代码实现

void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
int i = first, j = mid + 1;  
int m = mid,   n = last;  
int k = 0;  

while (i <= m && j <= n)  
{  
if (a[i] <= a[j])  
temp[k++] = a[i++];  
else  
temp[k++] = a[j++];  
}  

while (i <= m)  
temp[k++] = a[i++];  

while (j <= n)  
temp[k++] = a[j++];  

for (i = 0; i < k; i++)  
a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
if (first < last)  
{  
int mid = (first + last) / 2;  
mergesort(a, first, mid, temp);//左边有序  
mergesort(a, mid + 1, last, temp); //右边有序  
mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
}  
}  

bool MergeSort(int a[], int n)  
{  
int *p = new int[n];  
if (p == NULL)  
return false;  
mergesort(a, 0, n - 1, p);  
delete[] p;  
return true;  
}

参考文章