快速排序
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
快速排序实现
*/
int FindPos(int * a, int low, int high);
void QuickSort(int * a, int low, int high);
int main(void)
{
int a[6] = {-2, 1, 0, -985, 4, -93};
int i;
QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标 第三个参数表示最后一个元素的下标
for (i=0; i<6; ++i)
printf("%d ", a[i]);
printf("\n");
return 0;
}
void QuickSort(int * a, int low, int high)
{
int pos;
if (low < high)
{
pos = FindPos(a, low, high);
QuickSort(a, low, pos-1);
QuickSort(a, pos+1, high);
}
}
int FindPos(int * a, int low, int high)
{
int val = a[low];
while (low < high)
{
while (low<high && a[high]>=val)
--high;
a[low] = a[high];
while (low<high && a[low]<=val)
++low;
a[high] = a[low];
}//终止while循环之后low和high一定是相等的
a[low] = val;
return high; //high可以改为low, 但不能改为val 也不能改为a[low] 也不能改为a[high]
}
```
冒泡排序
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
冒泡排序实现
*/
int main()
{
int i=0,j=0,len=0,t=0;
int a[5]={1,10,50,30,61};
len=sizeof(a)/ sizeof(a[0]);
for(i=0;i<len-1;i++){
for(j=0;j<len-1-i;j++){
if(a[j]>a[j+1]){
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf("冒泡排序后的数据为：");
for(i=0;i<len;i++){
printf("%d ",a[i]);
}
}
```
插入排序
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
插入排序实现
*/
void InsertionSort(int *num,int n);
int main()
{
int i=0,len=0;
int a[5]= {1,10,50,30,61};
len=sizeof(a)/ sizeof(a[0]);
InsertionSort(a,len);
printf("插入排序后的数据为：");
for(i=0; i<len; i++)
{
printf("%d ",a[i]);
}
}
void InsertionSort(int *num,int n)
{
int i = 0;
int j = 0;
int tmp = 0;
for(i = 1; i<n; i++)
{
tmp = num[i];//从待插入组取出第一个元素。
j = i-1; //i-1即为有序组最后一个元素（与待插入元素相邻）的下标
while(j>=0&&tmp<num[j]) //注意判断条件为两个，j>=0对其进行边界限制。第二个为插入判断条件
{
num[j+1] = num[j];//若不是合适位置，有序组元素向后移动
j--;
}
num[j+1] = tmp;//找到合适位置，将元素插入。
}
}
```
选择排序
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
选择排序实现
*/
int main()
{
int a[6] = {-2, 1, 0, -985, 4, -93};
int len=sizeof(a)/ sizeof(a[0]);
for(int i=0;i<len;i++){
int min = i;//最小元素的下标
for(int j=i+1;j<len;j++){
if(a[j]<a[min]){
min = j;
}
}
int temp = a[i];
a[i]=a[min];
a[min] = temp;
}
printf("选择排序后的数据为：");
for(int i=0;i<len;i++){
printf("%d ",a[i]);
}
}
```
归并排序
```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
#define Max_ 10
// 打印结果
void Show(int arr[], int n)
{
int i;
for ( i=0; i<n; i++ )
printf("%d ", arr[i]);
printf("\n");
}
// 归并排序中的合并算法
void Merge(int array[], int left, int m, int right)
{
int aux[Max_] = {0}; // 临时数组 （若不使用临时数组，将两个有序数组合并为一个有序数组比较麻烦）
int i; //第一个数组索引
int j; //第二个数组索引
int k; //临时数组索引
for (i = left, j = m+1, k = 0; k <= right-left; k++) // 分别将 i, j, k 指向各自数组的首部。
{
//若 i 到达第一个数组的尾部，将第二个数组余下元素复制到 临时数组中
if (i == m+1)
{
aux[k] = array[j++];
continue;
}
//若 j 到达第二个数组的尾部，将第一个数组余下元素复制到 临时数组中
if (j == right+1)
{
aux[k] = array[i++];
continue;
}
//如果第一个数组的当前元素 比 第二个数组的当前元素小，将 第一个数组的当前元素复制到 临时数组中
if (array[i] < array[j])
{
aux[k] = array[i++];
}
//如果第二个数组的当前元素 比 第一个数组的当前元素小，将 第二个数组的当前元素复制到 临时数组中
else
{
aux[k] = array[j++];
}
}
//将有序的临时数组 元素 刷回 被排序的数组 array 中，
//i = left , 被排序的数组array 的起始位置
//j = 0， 临时数组的起始位置
for (i = left, j = 0; i <= right; i++, j++)
{
array[i] = aux[j];
}
}
// 归并排序
void MergeSort(int array[], int start, int end)
{
if (start < end)
{
int i;
i = (end + start) / 2;
// 对前半部分进行排序
MergeSort(array, start, i);
// 对后半部分进行排序
MergeSort(array, i + 1, end);
// 合并前后两部分
Merge(array, start, i, end);
}
}
int main()
{ //测试数据
int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
//排序前数组序列
Show( arr_test, Max_ );
MergeSort( arr_test, 0, Max_-1 );
//排序后数组序列
Show( arr_test, Max_ );
return 0;
}
```
希尔排序
```
void ShellSort(SqList *L)//下标0不存储元素，暂时存储元素使用
{
int i,j;
int increment=L->length;//增量值
do
{
increment=increment/3+1;
/*增量序列*/
for( i=increment+1; i<=L->length; i++ )
{
if (L->r[i]<L->r[i-increment])
{
/*需将L->r[i]插入有序增量子表*/
L->r[0]=L->r[i];/*暂存在L->r[0] */
for (j=i-increment; j>0&&L->r[0]<L->r[j]; j-=increment)
{
L->r[j+increment]=L->r[j];/*记录后移，查找插入位置*/
}
L->r[j+increment]=L->r[0]; /*插入*/
}
}
}
while (increment>1);
}
```
堆排序
```
package sortdemo;
import java.util.Arrays;
/**
* 堆排序demo
*/
public class HeapSort {
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
//1.构建大顶堆
for(int i=arr.length/2-1;i>=0;i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for(int j=arr.length-1;j>0;j--){
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对堆进行调整
}
}
/**
* 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
* @param arr
* @param i
* @param length
*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;//将temp值放到最终的位置
}
/**
* 交换元素
* @param arr
* @param a
* @param b
*/
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
```