排序算法分为内部排序和外部排序，我们经常说的排序算法就是内部排序
内部排序：数据记录在内存中进行排序
外部排序：排序的数据很大，一次性不能容纳全部的排序记录，在排序的过程中需要访问外存
稳定排序算法：相同的元素位置没有被改变
我们将要了解的排序算法如下：
交换排序：冒泡排序（可以是稳定，可以是不稳定），快速排序（不稳定）
选择排序：简单选择排序（不稳定），堆排序
插入排序：直接插入排序，希尔排序
归并排序
现在我们先来了解一下我们交换排序中的冒泡排序算法
冒泡排序
思想：
- 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
代码如下：
1 #include<stdio.h>
2 int a[5];
3 void swap(int a[],int i,int j)
4 {
5 int t=a[i];
6 a[i]=a[j];
7 a[j]=t;
8 }
9 void Bubblesort(int a[],int n)
10 {
11 int i,j;
12 for(i=0;i<n;i++)
13 {
14 for(j=i;j<n;j++)
15 {
16 if(a[i]>a[j])
17 {
18 swap(a,i,j);
19 }
20 }
21 }
22 }
23 int main()
24 {
25 int i;
26 for(i=0;i<5;i++)
27 {
28 scanf("%d",&a[i]);
29 }
30 Bubblesort(a,5);
31 for(i=0;i<5;i++)
32 {
33 printf("%d\n",a[i]);
34 }
35 return 0;
36 }
冒泡排序是最容易了解和掌握的排序算法，但是对于多元素的数据排序是没有效率的，但是冒泡排序也是可以改进的，下面我们看看冒泡排序的改进算法——鸡尾酒排序
此算法与冒泡排序算法的不同在于从上到下又从下到上，而冒泡排序仅仅是从上到下
下面我们看看鸡尾酒排序的算法
1 #include<stdio.h>
2 int a[5];
3 void swap(int a[],int i,int j)
4 {
5 int t=a[i];
6 a[i]=a[j];
7 a[j]=t;
8 }
9 void Bubblesort(int a[],int n)
10 {
11 int i;
12 int l=0,r=n-1;
13 while(l<r)
14 {
15 for(i=l;i<r;i++)
16 {
17 if(a[i]>a[i+1])//max,down将最大值放到底部
18 {
19 swap(a,i,i+1);
20 }
21 }
22 r--;//因为是放到底部所以是r--
23 for(i=r;i>l;i--)
24 {
25 if(a[i-1]>a[i])//min up将最小值放到顶部
26 {
27 swap(a,i-1,i);
28 }
29 }
30 l++;//放到底部，所以l++
31 }
32 }
33 int main()
34 {
35 int i;
36 for(i=0;i<5;i++)
37 {
38 scanf("%d",&a[i]);
39 }
40 Bubblesort(a,5);
41 for(i=0;i<5;i++)
42 {
43 printf("%d\n",a[i]);
44 }
45 return 0;
46 }
下面我们看看交换排序中的快速排序
快速排序：
思想：
快速排序主要运用的是递归的思想
快速排序采用分冶法将一个序列分为两个子序列
1.从序列中挑取一个元素作为基准元素
2.把所有比基准小的元素放基准元素的前面，把比基准元素大的放基准元素的后面，相同的可以方任意一边，这个操作叫做分区操作
3.对每个分区递归进行操作1，2，递归结束的条件是序列大小为0或者1。
代码如下：
1 #include<stdio.h>
2 #define p 10
3 int a[p];
4 void swap(int a[],int i,int j)
5 {
6 int t=a[i];
7 a[i]=a[j];
8 a[j]=t;
9 }
10 int Divide(int a[],int l,int r)//划分序列
11 {
12 int benchmark=a[r];//确定基准元素
13 int tail=l-1;//初始化
14 int i;
15 for(i=l;i<r;i++)//遍历除了基准元素以外的全部元素
16 {
17 if(a[i]<=benchmark)//把小于基准元素的放左边
18 {
19 swap(a,++tail,i);
20 }
21 }
22 swap(a,tail+1,r);//把基准元素放到所有比基准元素小的元素后边
23 return tail+1;//返回索引
24 }
25 void Quicksort(int a[],int l,int r)
26 {
27 if(l>=r)//存在序列大小为0或者为1
28 return;
29 int index=Divide(a,l,r);//第一次初始化划分序列，且确定基准元素
30 Quicksort(a,l,index-1);
31 Quicksort(a,index+1,r);
32 }
33 int main()
34 {
35 int i;
36 for(i=0;i<p;i++)
37 {
38 scanf("%d",&a[i]);
39 }
40 Quicksort(a,0,p-1);
41 for(i=0;i<p;i++)
42 {
43 printf("%d\n",a[i]);
44 }
45 return 0;
46 }
下面我们来看看选择排序，先看看选择排序中的简单的选择排序
简单选择排序：
思想:
简单选择排序就是遍历元素，找到当且元素最大或者最小的拿出来，放到自己数组头部，后面找到的数组放数组第1位，2位，以此类推，然后遍历范围减1，一直循环下去，直到遍历范围为1
但是我们要注意简单选择排序和冒泡排序的区别：冒泡排序是相邻的两个元素交换，而选择排序则不是
话不多说，下面我们直接看代码：
1 #include<stdio.h>
2 #define p 10
3 int a[p];
4 void swap(int a[],int i,int j)
5 {
6 int t=a[i];
7 a[i]=a[j];
8 a[j]=t;
9 }
10 void selectsort(int a[],int n)
11 {
12 int i,j,min;
13 for(i=0;i<n;i++)
14 {
15 min=i;//假定最小元素的位置
16 for(j=i+1;j<n;j++)//遍历最小元素后面的元素，找到第最小元素的位置
17 {
18 if(a[min]>a[j])
19 {
20 min=j;
21 }
22 }
23 if(min!=i)//交换
24 {
25 swap(a,min,i);
26 }
27 }
28 }
29 int main()
30 {
31 int i;
32 for(i=0;i<p;i++)
33 {
34 scanf("%d",&a[i]);
35 }
36 selectsort(a,p);
37 for(i=0;i<p;i++)
38 {
39 printf("%d\n",a[i]);
40 }
41 return 0;
42 }
下面我们来看看选择排序中的堆排序：
堆排序：
堆排序要借助于堆这种数据结构，主要分两步走，第一步是构造初始堆，第二个输出堆顶元素之后堆怎么调整
我们以大定堆为例：要求其中父节点的值总是大于子节点
1 #include<stdio.h>
2 #define p 10
3 int a[p];
4 void swap(int a[],int i,int j)
5 {
6 int t=a[i];
7 a[i]=a[j];
8 a[j]=t;
9 }
10 int Adjustment(int a[],int i,int size)//堆的调整
11 {
12 int left_child=2*i+1;
13 int right_child=2*i+2;//确定左右孩子位置
14 int max=i;//若孩子大于父亲，则交换
15 if(left_child<size&&a[left_child]>a[max])
16 max=left_child;
17 if(right_child<size&&a[right_child]>a[max])
18 max=right_child;
19 if(max!=i)
20 {
21 swap(a,max,i);
22 Adjustment(a,max,size);
23 }
24 }
25 int BuildHeap(int a,int n)
26 {
27 int size=n;
28 int i;
29 for(i=size/2-1;i>=0;i--)//建立最大堆
30 {
31 Adjustment(a,i,size);
32 }
33 return size;
34 }
35 void Heapsort(int a,int n)//堆排序算法
36 {
37 int size=BuildHeap(a,n);
38 while(size>1)
39 {
40 swap(a,0,--size);//将堆顶元素与最末尾的元素进行交换，升序排列
41 Adjustment(a,0,size);
42 }
43 }
44 int main()
45 {
46 int i;
47 for(i=0;i<p;i++)
48 {
49 scanf("%d",&a[i]);
50 }
51 Heapsort(a,p);
52 for(i=0;i<p;i++)
53 {
54 printf("%d\n",a[i]);
55 }
56 return 0;
57 }
TRANSLATE with