1、常见排序算法大致有以下几种：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序
2、各种排序算法的实现逻辑可简单描述如下：
冒泡排序：不想说了
选择排序：从前往后找到最大的一个与最后一个交换
插入排序：从第二个数开始，认为前面是一个有序数列向前插入
希尔排序： 以n/2为步长分组，插入排序
归并排序 ： 二分法递归，合并两个有序数组
快速排序 ： 第一个为中间值，从右往左找最比中间值小的放左边，从左往右找比中间值大的放右边，左右交叉时第一个放交叉处，递归交叉处左边，递归交叉处右边
堆排序 ： 递归左比较父子大小并交换， 递归右比较父子大小并交换，重建左堆，重建右侧堆
桶排序 ：数据分块儿，常用于大数据。
3、上代码：
//插入排序
void insertFun(int A[], int n)
{
for (int i=1; i<n; i++) {
int k=i;
while (k>=1&&A[k]<A[k-1]) {
swap(&A[k],&A[k-1]);
k--;
}
}
}
//归并排序
void merge(int *a,int n,int begin,int end)
{
if (end-begin<=1) {
return;
}
merge(a,n,begin,begin+(end-begin+1)/2);
merge(a,n,begin+(end-begin+1)/2+1,end);
hebing(a,n,begin+(end-begin+1)/2+1,end);
}
//冒泡排序
void funPaoCompare(int *a,int n,int begin,int end)
{
for (int i=begin; i<end+1; i++) {
for (int j=begin; j<end+1-1-i; j++) {
count++;
if (a[j]>a[j+1]) {
swap(&a[j], &a[j+1]);
}
}
}
}
//选择排序
void selectFun(int A[], int n)
{
for (int i=0; i<n; i++) {
int minIndex=i;
for (int j=i+1; j<n; j++) {
if (A[minIndex]>A[j]) {
minIndex = j;
}
}
if (minIndex!=i) {
swap(&A[minIndex], &A[i]);
}
}
}
//希尔排序
void shellFun(int A[], int n)
{
int w = n;
while(floor(w/2)>=1)
{
w=floor(w/2);
shellFun_detail(A,n,w);
}
}
void shellFun_detail(int A[], int n, int s)
{
for (int i=0; i<n; i+=s) {
int k=i;
for (int j=i-s; j>=0; j-=s) {
if (A[k]<A[j]) {
swap(&A[k], &A[j]);
k=j;
}
else
{
break;
}
}
}
}
//快速排序
void quickPai(int *a,int n,int begin,int end)
{
if (end-begin<=0) {
return;
}
if (end-begin==1&&a[begin]>a[end]) {
swap(&a[begin], &a[end]);
return;
}
int length = end-begin+1;
int compare = begin,now = end;
for (int i=begin;i<begin+length;i++) {
if (compare<now&&a[compare]>a[now]) {
swap(&a[compare],&a[now]);
int temp = compare;
compare = now;
now = temp+1;
}
else if (compare>now&&a[compare]<a[now]) {
swap(&a[compare],&a[now]);
int temp = compare;
compare = now;
now = temp-1;
}
else if(compare<now)
{
now--;
}
else if (compare>now)
{
now++;
}
}
quickPai(a,n,begin,compare-1);
quickPai(a,n,compare+1,end);
}
//堆排序
void heap(int A[], int n, int s)
{
if (left(s)>n&&right(s)>n) {
return ;
}
if (left(s)<=n) {
heap(A, n, left(s));
}
if (right(s)<=n) {
heap(A, n, right(s));
}
int min = s;
if (A[left(s)-1]<A[min-1]) {
min =left(s);
}
if (A[right(s)-1]<A[min-1]) {
min =right(s);
}
if (min!=s) {
swap(&A[min-1],&A[s-1]);
heap(A, n, left(s));
heap(A, n, right(s));
}
}
int left(int a)
{
return 2*a;
}
int right(int a)
{
return 2*a+1;
}
void swap(int *a, int *b)
{
*a=*a^*b;
*b=*b^*a;
*a=*a^*b;
}
//输出
void fun_out(int A[], int n)
{
for (int i=0; i<n; i++) {
NSLog(@"%i",A[i]);
}
}
4、其他相关算法
//合并两个有序数列
void heBing(int a[],int m,int b[],int n,int c[])
{ int i=0,j=0,w=0;
while (i<m&&j<n) {
if (a[i]<b[j]) {
c[w]=a[i];i++;w++;
}
else
{
c[w]=b[j];j++;w++;
}
}
while (i<m)
{
c[w]=a[i];i++;w++;
}
while (j<n)
{
c[w]=b[j];j++;w++;
}
}
