冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
时间复杂度O(n2)
void bubble_sort(int *array,int len) { int i = 0 ; int j = 0 ; int temp = 0; for(i = len; i > 0;i--) { for(j = 1;j < i;j++) { if(array[j-1] > array[j]) { temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; } } } }
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
时间复杂度O（n2）
/* * 从第一个元素开始，该元素可以认为已经被排序 * 取出下一个元素，在已经排序的元素序列中从后向前扫描 * 如果该元素（已排序）大于新元素，将该元素移到下一位置 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 * 将新元素插入到该位置后 * 最优的时间O(n) * 最坏的时间O(n2) * 平均的时间O(n2) */ void insert_sort(int *array,int len) { int i = 0 ; int j = 0 ; int temp = 0; for(i = 1; i < len;i++) { temp = array[i]; for(j = i;j > 0 && array[j-1] > temp;j--) array[j] = array[j-1]; array[j] = temp; } }
归并排序
是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
分治图：
两个有序数组合并的具体过程：
时间复杂度O(n * log2(n))
/* 分解：将n个元素分成各含n/2个元素的子序列 * 解决：用合并排序法对两个子序列递归地排序 * 合并：合并两个已排序的子序列以得到排序结果 * 时间复杂度O(n*log2(n)) */ void merge_sort_recursive(int arr[], int reg[], int left, int right) { if (left >= right) return; int len = right - left, mid = (len >> 1) + left; int left1 = left, right1 = mid; int left2 = mid + 1, right2 = right; merge_sort_recursive(arr, reg, left1, right1); merge_sort_recursive(arr, reg, left2, right2); int k = left; while (left1 <= right1 && left2 <= right2) reg[k++] = arr[left1] < arr[left2] ? arr[left1++] : arr[left2++]; while (left1 <= right1) reg[k++] = arr[left1++]; while (left2 <= right2) reg[k++] = arr[left2++]; for (k = left; k <= right; k++) arr[k] = reg[k]; } void merge_sort(int arr[], const int len) { int reg[len]; merge_sort_recursive(arr, reg, 0, len - 1); }
二叉堆排序
static void swap(int *a,int *b) { int index = *a; *a = *b; *b = index; } /* *假设"第一个元素"在数组中的索引为 0 的话，则父节点和子节点的位置关系如下： *(01) 索引为i的左孩子的索引是 (2*i+1); *(02) 索引为i的左孩子的索引是 (2*i+2); *(03) 索引为i的父结点的索引是 floor((i-1)/2); */ /*自上而下*/ void max_heapify(int array[], int start, int end) { printf("start is %d ",start); int parent = start; int child = parent * 2 + 1;//左孩子 while(child <= end) { if(child + 1 <= end && array[child] < array[child+1]) child++; if(array[parent] > array[child]) return; else{ swap(&array[parent],&array[child]); parent = child; child = (parent << 1) + 1; } } } void heap_sort(int array[],int len) { /* 初始化，i从最后一个根节点节点开始调整,自下而上，a[0]是根节点*/ for(int i = len/2-1;i >= 0; i--) max_heapify(array,i,len-1); for(int i = len -1;i >= 0;i--) { //将第一个元素和已经排好元素前一位做交换，再重新排序 swap(&array[0],&array[i]); max_heapify(array, 0, i - 1); } }
快速排序
static void swap(int *a,int *b) { int index = *a; *a = *b; *b = index; } static int median3(int *array,int left,int right) { int center = (left + right) >> 1; if(array[left] > array[center]) swap(&array[left],&array[center]); if(array[left] > array[right]) swap(&array[left],&array[right]); if(array[center] > array[right]) swap(&array[center],&array[right]); /* array[left] < array[center] < array[right]*/ return array[center]; } static void quick_array(int *array,int left,int right) { int i; int j; int privot; int center; if((right-left) >= 2) { privot = median3(array,left,right); center = (left + right) >> 1; printf("left center right ---> %d %d %d ",array[left],array[center],array[right]); swap(&array[center],&array[right-1]); for(int i = 0;i < 10 ; i++) printf("array[%d] = %d ",i,array[i]); printf(" "); i = left; j = right - 1; for(;;) { while(array[++i] < privot); while(array[--j] > privot); if(i < j) swap(&array[i],&array[j]); else break; } swap(&array[i],&array[right-1]); quick_array(array,left,i-1); quick_array(array,i+1,right); }else{ if((right-left) == 0) return; else if((right-left) == 1) { if(array[left] > array[right]) swap(&array[left],&array[right]); } } } void quick_sort(int *array,int len) { quick_array(array,0,len-1); }