c語言排序方法有：1、簡單選擇排序，基於O（n2）時間複雜度的排序演算法；2、冒泡排序；3、簡單插入排序；4、希爾排序；5、歸併排序，基於歸併操作的一種排序演算法；6、快速排序，屬於分治法的一種；7、堆排序等。
本教學操作環境：windows7系統、C 17版本、Dell G3電腦。
1.選擇排序-簡單選擇排序
選擇排序是最簡單的一種基於O（n2）時間複雜度的排序演算法，基本思想是從i=0位置開始到i=n-1每次透過內循環找出i位置到n-1位置的最小（大）值。
演算法實作：
void selectSort(int arr[], int n)
{ int i, j , minValue, tmp; for(i = 0; i < n-1; i++)
{
minValue = i; for(j = i + 1; j < n; j++)
{ if(arr[minValue] > arr[j])
{
minValue = j;
}
} if(minValue != i)
{
tmp = arr[i];
arr[i] = arr[minValue];
arr[minValue] = tmp;
}
}
}void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n");
}void main()
{ int arr[10] = {2,5,6,4,3,7,9,8,1,0};
printArray(arr, 10);
selectSort(arr, 10);
printArray(arr, 10); return;
}登入後複製
如實作所示，簡單的選擇排序複雜度固定為O(n2)，每次內迴圈找出沒有排序數列中的最小值，然後跟著目前資料交換。由於選擇排序透過尋找最值的方式排序，循環次數幾乎是固定的，一種最佳化方式是每次循環同時找到最大值和最小值可以是循環次數減少為（n/2），只是在循環中添加了記錄最大值的操作，原理一樣，本文不再對此方法實現。
2.冒泡排序
冒泡排序在一組需要排序的數組中，對兩兩數據順序與要求順序相反時，交換數據，使大的數據向後移，每趟排序將最大的數字放在最後的位置上，如下：
#演算法實作：
void bubbleSort(int arr[], int n)
{ int i, j, tmp; for(i = 0; i < n - 1; i++)
{ for(j = 1; j < n; j++)
{ if(arr[j] < arr[j - 1])
{
tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
}
}
}void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n");
}void main()
{ int arr[10] = {2,5,6,4,3,7,9,8,1,0};
printArray(arr, 10);
bubbleSort(arr, 10);
printArray(arr, 10); return;
}登入後複製
如上是一種最簡單的實現方式，需要注意的可能是i, j的邊界問題，這種方式固定循環次數，肯定可以解決各種情況，不過演算法的目的是為了提升效率，根據冒泡排序的過程圖可以看出這個演算法至少可以從兩點進行最佳化：
1) 對於外層循環，如果當前序列已經有序，即不再進行交換，應該不再進行接下來的循環直接跳出。
2)對於內層循環後面最大值已經有序的情況下應該不再進行循環。
最佳化程式碼實作：
void bubbleSort_1(int arr[], int n)
{ int i, nflag, tmp; do
{
nflag = 0; for(i = 0; i < n - 1; i++)
{ if(arr[i] > arr[i + 1])
{
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
nflag = i + 1;
}
}
n = nflag;
}while(nflag);
}登入後複製
如上，當nflag為0時，表示本次循環沒有發生交換，序列已經有序不用再循環，如果nflag>0則記錄了最後一次發生交換的位置，此位置以後的序列都是有序的，循環不再往後進行。
3.插入排序-簡單插入排序
插入排序是將一個記錄插入到已經有序的序列中，得到一個新的元素加一的有序序列，實現上即將第一個元素看成一個有順序的序列，從第二個元素開始逐一插入得到一個完整的有序序列，插入過程如下：
##如圖，插入排序第i個元素與相鄰前一個元素比較，如果與排序順序相反則與前一個元素交換位置，循環直到合適的位置。
演算法實作：
void insertSort(int arr[], int n)
{ int i, j, tmp; for(i = 1; i < n; i++)
{ for(j = i; j > 0; j--)
{ if(arr[j] < arr[j-1])
{
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
} else
{ break;
}
}
} return;
}void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}void main()
{ int arr[10] = {2,5,6,4,3,7,9,8,1,0};
printArray(arr, 10);
insertSort(arr, 10);
printArray(arr, 10); return;
}登入後複製
如上，前面提到選擇排序不管什麼情況下都是固定為O(n2)的演算法，插入演算法雖然也是O(n2)的演算法，不過可以看出，在已經有順序的情況下，插入可以直接跳出循環，在極端情況下（完全有序）插入排序可以是O（n）的演算法。不過在實際完全亂序的測試案例中，與本文中的選擇排序相比，相同序列的情況下發現插入排序運行的時間比選擇排序長，這是因為選擇排序每次外循環只與選擇的最值進行交換，而插入排序則需要不停與相鄰元素交換知道合適的位置，交換的三次賦值操作同樣影響運行時間，因此下面對這一點進行優化：
優化後實現：
void insertSort_1(int arr[], int n)
{ int i, j, tmp, elem; for(i = 1; i < n; i++)
{
elem = arr[i]; for(j = i; j > 0; j--)
{ if(elem < arr[j-1])
{
arr[j] = arr[j-1];
} else
{ break;
}
}
arr[j] = elem;
} return;
}登入後複製
最佳化程式碼將需要插入的值快取下來，將插入位置之後的元素向後移一位，將交換的三次賦值改為一次賦值，減少執行時間。
4.插入排序-希爾排序
希爾排序的基本想法是先取一個小於n的整數d1作為第一個增量，把全部元素分組。所有距離為d1的倍數的記錄放在同一個組別中。先在各組內進行直接插入排序；然後，取第二個增量d2 < d1重複上述的分組和排序，直至所取的增量=1( < …< d2 < d1)，即所有記錄放在同一組中進行直接插入排序為止，希爾排序主要是根據插入排序的一下兩種性質對插入排序進行改進：
1)插入排序在對幾乎已經排好序的資料操作時，效率高，即可達到線性排序的效率。
2)但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
排序过程如下：
算法实现：基于一种简单的增量分组方式｛n/2,n/4,n/8……,1｝
void shellSort(int arr[], int n)
{ int i, j, elem; int k = n/2; while(k>=1)
{ for(i = k; i < n; i ++)
{
elem = arr[i]; for(j = i; j >= k; j-=k)
{ if(elem < arr[j-k])
{
arr[j] = arr[j-k];
} else
{ break;
}
}
arr[j] = elem;
}
k = k/2;
}
}void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}void main()
{ int arr[10] = {2,5,6,4,3,7,9,8,1,0};
printArray(arr, 10);
shellSort(arr, 10);
printArray(arr, 10); return;
}登入後複製
5.归并排序
归并排序是基于归并操作的一种排序算法，归并操作的原理就是将一组有序的子序列合并成一个完整的有序序列，即首先需要把一个序列分成多个有序的子序列，通过分解到每个子序列只有一个元素时，每个子序列都是有序的，在通过归并各个子序列得到一个完整的序列。
合并过程：
把序列中每个单独元素看作一个有序序列，每两个单独序列归并为一个具有两个元素的有序序列，每两个有两个元素的序列归并为一个四个元素的序列依次类推。两个序列归并为一个序列的方式：因为两个子序列都是有序的（假设由小到大），所有每个子序列最左边都是序列中最小的值，整个序列最小值只需要比较两个序列最左边的值，所以归并的过程不停取子序列最左边值中的最小值放到新的序列中，两个子序列值取完后就得到一个有序的完整序列。
归并的算法实现：
void merge(int arr[], int l, int mid, int r)
{ int len,i, pl, pr; int *tmp = NULL;
len = r - l + 1;
tmp = (int*)malloc(len * sizeof(int)); //申请存放完整序列内存
memset(tmp, 0x0, len * sizeof(int));
pl = l;
pr = mid + 1;
i = 0; while(pl <= mid && pr <= r) //两个子序列都有值，比较最小值
{ if(arr[pl] < arr[pr])
{
tmp[i++] = arr[pl++];
} else
{
tmp[i++] = arr[pr++];
}
} while(pl <= mid) //左边子序列还有值，直接拷贝到新序列中
{
tmp[i++] = arr[pl++];
} while(pr <= r) //右边子序列还有值
{
tmp[i++] = arr[pr++];
} for(i = 0; i < len; i++)
{
arr[i+l] = tmp[i];
} free(tmp); return;
}登入後複製
归并的迭代算法：
迭代算法如上面所说，从单个元素开始合并，子序列长度不停增加直到得到一个长度为n的完整序列。
#include<stdio.h>#include<stdlib.h>#include<string.h>void merge(int arr[], int l, int mid, int r)
{ int len,i, pl, pr; int *tmp = NULL;
len = r - l + 1;
tmp = (int*)malloc(len * sizeof(int)); //申请存放完整序列内存
memset(tmp, 0x0, len * sizeof(int));
pl = l;
pr = mid + 1;
i = 0; while(pl <= mid && pr <= r) //两个子序列都有值，比较最小值
{ if(arr[pl] < arr[pr])
{
tmp[i++] = arr[pl++];
} else
{
tmp[i++] = arr[pr++];
}
} while(pl <= mid) //左边子序列还有值，直接拷贝到新序列中
{
tmp[i++] = arr[pl++];
} while(pr <= r) //右边子序列还有值
{
tmp[i++] = arr[pr++];
} for(i = 0; i < len; i++)
{
arr[i+l] = tmp[i];
} free(tmp); return;
}int min(int x, int y)
{ return (x > y)? y : x;
}/*
归并完成的条件是得到子序列长度等于n，用sz表示当前子序列的长度。从1开始每次翻倍直到等于n。根据上面归并的方法，从i=0开始分组，下一组坐标应该i + 2*sz，第i组第一个元素为arr[i],最右边元素应该为arr[i+2*sz -1]，遇到序列最右边元素不够分组的元素个数时应该取n-1,中间的元素为arr[i+sz -1],依次类推进行归并得到完整的序列
*/void mergeSortBu(int arr[], int n)
{ int sz, i, mid,l, r; for(sz = 1; sz < n; sz+=sz)
{ for(i = 0; i < n - sz; i += 2*sz)
{
l = i;
r = i + sz + sz;
mid = i + sz -1;
merge(arr, l, mid, min(r-1, n-1));
}
} return;
}void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}void main()
{ int arr[10] = {2,5,6,4,3,7,9,8,1,0};
printArray(arr, 10);
mergeSortBu(arr, 10);
printArray(arr, 10); return;
}登入後複製
另一种是通过递归的方式，递归方式可以理解为至顶向下的操作，即先将完整序列不停分解为子序列，然后在将子序列归并为完整序列。
递归算法实现：
void mergeSort(int arr[], int l, int r)
{ if(l >= r)
{
return;
} int mid = (l + r)/2;
mergeSort(arr, l, mid);
mergeSort(arr, mid+1, r);
merge(arr, l, mid, r);
return;
}登入後複製
对于归并算法大家可以考虑到由于子序列都是有序的，所有如果左边序列的最大值都比右边序列的最小值小，那么整个序列就是有序的，不需要进行merge操作，因此可以在每次merge操作加一个if(arr[mid] > arr[mid+1])判断进行优化,这种优化对于近乎有序的序列非常有效果，不过对于一般的情况会有一次判断的额外开销，可以根据具体情况处理。
6.快速排序
快速排序跟归并排序类似属于分治法的一种，基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
排序过程如图：
因此，快速排序每次排序将一个序列分为两部分，左边部分都小于等于右边部分，然后在递归对左右两部分进行快速排序直到每部分元素个数为1时则整个序列都是有序的，因此快速排序主要问题在怎样将一个序列分成两部分，其中一部分所有元素都小于另一部分，对于这一块操作我们叫做partition,原理是先选取序列中的一个元素做参考量，比它小的都放在序列左边，比它大的都放在序列右边。
算法实现：
快速排序-单路快排：
如上：我们选取第一个元素v作为参考量及arr[l],定义j变量为两部分分割哨兵，变量i从l+1开始遍历每个变量，如果当前变量e > v则i++检测下一个元素，如果当前变量e < v 则e与arr[j+1]交换，可以看到arr[j+1]由交换前大于v变成小于v arr[i]变成大于v，同时对i++，j++，始终保持：arr[l+1….j] < v, arr[j+1….i-1] > v
代码实现：
#include <stdio.h>void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}void swap(int *a, int *b)
{ int tmp;
tmp = *a;
*a = *b;
*b = tmp; return;
}//arr[l+1...j] < arr[l], arr[j+1,..i)>arr[l]static int partition(int arr[], int l, int r)
{ int i, j;
i = l + 1;
j = l; while(i <= r)
{ if(arr[i] > arr[l])
{
i++;
} else
{
swap(&arr[j + 1], &arr[i]);
i++;
j++;
}
}
swap(&arr[l], &arr[j]); return j;
}static void _quickSort(int arr[], int l, int r)
{ int key; if(l >= r)
{ return;
}
key = partition(arr, l, r);
_quickSort(arr, l, key - 1);
_quickSort(arr, key + 1, r);
}void quickSort(int arr[], int n)
{
_quickSort(arr, 0, n - 1); return;
}void main()
{ int arr[10] = {1,5,9,8,7,6,3,4,0,2};
printArray(arr, 10);
quickSort(arr, 10);
printArray(arr, 10);
}登入後複製
因为有变量i从左到右依次遍历序列元素，所有这种方式叫单路快排，不过细心的同学可以发现我们忽略了考虑e等于v的情况，这种快排方式一大缺点就是对于高重复率的序列即大量e等于v的情况会退化为O（n2）算法，原因在大量e等于v的情况划分情况会如下图两种情况：
解决这种问题的一另种方法：
快速排序-两路快排：
两路快排通过i和j同时向中间遍历元素，e==v的元素分布在左右两个部分，不至于在多重复元素时划分严重失衡。依旧去第一个元素arr[l]为参考量，始终保持arr[l+1….i) <= arr[l], arr(j…r] >=arr[l]原则.
代码实现：
//arr[l+1....i) <=arr[l], arr(j...r] >=arr[l]static int partition2(int arr[], int l, int r)
{ int i, j;
i = l + 1 ;
j = r; while(i <= j)
{ while(i <= j && arr[j] > arr[l]) /*注意arr[j] >arr[l] 不是arr[j] >= arr[l]*/
{
j--;
} while(i <= j && arr[i] < arr[l])
{
i++;
} if(i < j)
{
swap(&arr[i], &arr[j]);
i++;
j--;
}
}
swap(&arr[j],&arr[l]); return j;
}登入後複製
针对重复元素比较多的情况还有一种实现方式：
快速排序-三路快排：
三路快排是在两路快排的基础上对e==v的情况做单独的处理，对于重复元素非常多的情况优势很大：
如上：取arr[l]为参考量，定义变量lt为小于v和等于v的分割点，变量i为遍历指针，gt为大于v和未遍历元素分割点，gt指向未遍历元素，边界条件跟个人定义有关本文始终保持arr[l+1…lt] < v,arr[lt+1….i-1],arr(gt…..r]>v的状态。
代码实现：
#include <stdio.h>void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}
void swap(int *a, int *b)
{ int tmp;
tmp = *a; *a = *b; *b = tmp; return;
}
static void _quickSort3(int arr [ ],int l,int r)
{ int i, lt, gt; if(l >= r)
{ return;
}
i = l + 1; lt = l; gt = r ; while(i <= gt)
{ if(arr[i] < arr[l])
{
swap(&arr[lt + 1], &arr[i]); lt ++;
i++;
} else if(arr[i] > arr[l])
{
swap(&arr[i], &arr[gt]); gt--;
} else
{
i++;
}
}
swap(&arr[l], &arr[gt]);
_quickSort3(arr, l, lt);
_quickSort3(arr, gt + 1, r); return;
}
void quickSort(int arr[], int n)
{
_quickSort3(arr, 0, n - 1); return;
}
void main()
{ int arr[10] = {1,5,9,8,7,6,3,4,0,2};
printArray(arr, 10);
quickSort(arr, 10);
printArray(arr, 10);
}登入後複製
三路快排在重复率比较高的情况下比前两种有较大优势，但就完全随机情况略差于两路快排，可以根据具体情况进行合理选择，另外本文在选取参考值时为了方便一直选择第一个元素为参考值，这种方式对于近乎有序的序列算法会退化到O（n2），因此一般选取参考值可以随机选择参考值或者其他选择参考值的方法然后再与arr[l]交换，依旧可以使用相同的算法。
7.堆排序
堆其实一种树形结构，以二叉堆为例，是一颗完全二叉树（即除最后一层外每个节点都有两个子节点，且非满的二叉树叶节点都在最后一层的左边位置），二叉树满足每个节点都大于等于他的子节点(大顶堆)或者每个节点都小于等于他的子节点（小顶堆），根据堆的定义可以得到堆满足顶点一定是整个序列的最大值（大顶堆）或者最小值（小顶堆）。如下图：
堆排序就是一种基于堆得选择排序，先将需要排序的序列构建成堆，在每次选取堆顶点的最大值和最小值知道完成整个堆的遍历。
用数组表示堆：
二叉堆作为树的一种，通常用结构体表示，为了排序的方便，我们通常使用数组来表示堆，如下图：
将一个堆按图中的方式按层编号可以得到如下结论：
1）节点的父节点编号满足parent(i) = i/2
2）节点的左孩子编号满足 left child (i) = 2*i
3）节点右孩子满足 right child (i) = 2*i + 1
由于数组编号是从0开始对上面结论修改得到：
parent(i) = (i-1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2
堆的两种操作方式：
根据堆的主要性质（父节点大于两个子节点或者小于两个子节点），可以得到堆的两种主要操作方式，以大顶堆为例：
a）如果子节点大于父节点将子节点上移（shift up）
b）如果父节点小于两个子节点中的最大值则父节点下移（shift down）
shift up:
如果往已经建好的堆中添加一个元素，如下图，此时不再满足堆的性质，堆遭到破坏，就需要执行shift up 操作将添加的元素上移调整直到满足堆的性质。
调整堆的方法：
1）7号位新增元素48与其父节点[i/2]=3比较大于父节点的32不满足堆性质，将其与父节点交换。
2）此时新增元素在3号位，再与3号位父节点[i/2]=1比较，小于1号位的62满足堆性质，不再交换，如果此步骤依旧不满足堆性质则重复1步骤直到满足堆的性质或者到根节点。
3）堆调整完成。
代码实现：
代码中基于数组实现，数组下表从0开始，父子节点关系如用数组表示堆
/*parent(i) = (i-1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2*/void swap(int *a, int *b)
{ int tmp;
tmp = *a; *a = *b; *b = tmp; return;
}
void shiftUp(int arr[], int n, int k)
{ while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2])
{
swap(&arr[k], &arr[(k-1)/2]);
k = (k - 1)/2;
} return;
}登入後複製
shift down:
与shift up相反，如果从一个建好的堆中删除一个元素，此时不再满足堆的性质，此时应该怎样来调整堆呢？
如上图，将堆中根节点元素62删除调整堆的步骤为：
1）将最后一个元素移到删除节点的位置
2）与删除节点两个子节点中较大的子节点比较，如果节点小于较大的子节点，与子节点交换，否则满足堆性质，完成调整。
3）重复步骤2，直到满足堆性质或者已经为叶节点。
4）完成堆调整
代码实现：
void shiftDown(int arr[], int n, int k)
{ int j = 0 ; while(2*k + 1 < n)
{
j = 2 *k + 1; //标记两个子节点较大的节点，初始为左节点
if (j + 1 < n && arr[j] < arr[j+1])
{
j ++;
} if(arr[k] < arr[j])
{
swap(&arr[k], &arr[j]);
k = j;
} else
{ break;
}
} return;
}登入後複製
知道了上面两种堆的操作后，堆排序的过程就非常简单了
1）首先将待排序序列建成堆，由于最后一层即叶节点没有子节点所以可以看成满足堆性质的节点，第一个可能出现不满足堆性质的节点在第一个父节点的位置，假设最后一个叶子节点为（n - 1） 则第一个父节点位置为(n-1-1)/2,只需要依次对第一个父节点之前的节点执行shift down操作到根节点后建堆完成。
2）建堆完成后（以大顶堆为例）第一个元素arr[0]必定为序列中最大值，将最大值提取出来（与数组最后一个元素交换），此时堆不再满足堆性质，再对根节点进行shift down操作，依次循环直到根节点，排序完成。
代码实现：
#include/*parent(i) = (i-1)/2
left child (i) = 2*i + 1
right child (i) = 2*i + 2*/void swap(int *a, int *b)
{ int tmp;
tmp = *a; *a = *b; *b = tmp; return;
}
void shiftUp(int arr[], int n, int k)
{ while((k - 1)/2 >= 0 && arr[k] > arr[(k - 1)/2])
{
swap(&arr[k], &arr[(k-1)/2]);
k = (k - 1)/2;
} return;
}
void shiftDown(int arr[], int n, int k)
{ int j = 0 ; while(2*k + 1 < n)
{
j = 2 *k + 1; if (j + 1 < n && arr[j] < arr[j+1])
{
j ++;
} if(arr[k] < arr[j])
{
swap(&arr[k], &arr[j]);
k = j;
} else
{ break;
}
} return;
}
void heapSort(int arr[], int n)
{ int i = 0; for(i = (n - 1 -1)/2; i >=0; i--)
{
shiftDown(arr, n, i);
} for(i = n - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
shiftDown(arr, i, 0);
} return;
}
void printArray(int arr[], int n)
{ int i; for(i = 0; i < n; i++)
{ printf("%d ", arr[i]);
} printf("\n"); return;
}
void main()
{ int arr[10] = {1,5,9,8,7,6,3,4,0,2};
printArray(arr, 10);
heapSort(arr, 10);
printArray(arr, 10);
}
登入後複製
推荐教程：《C#》
以上是c語言排序方法有哪幾種的詳細內容。更多資訊請關注PHP中文網其他相關文章！
