标签：二叉树 gif 简单选择排序 ide i++ free root inf adjust
写在前面：在我们找工作的过程中，经常会被问到是否了解常见的算法，所以，如果想在面试过程中有个良好的表现，对常见的排序算法有一定的了解是必须的。
七种常见排序算法总结
第一类：交换排序
1、冒泡排序
原理说明：
（1）比较相邻的元素，如果第一个比第二个大，就交换它们两个；
（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
（3）针对所有的元素重复以上的步骤，除了最后一个；
（4）重复步骤1~3，直到排序完成。
代码实现：
1 #include 2
3 int main()
4 {
5 int A[]={6,5,3,1,8,7,2,4};
6 int n=sizeof(A)/sizeof(int);
7 //从小到大
8 int tmp=0;
9 for(int i=0;i1;i++)
10 {
11 for(int j=0;j1-i;j++)
12 {
13 if(A[j]>A[j+1])
14 {
15 tmp=A[j];
16 A[j]=A[j+1];
17 A[j+1]=tmp;
18 }
19 }
20 }
21 for(int i=0;i)
22 {
23 printf("%d ",A[i]);
24 }
25 return 0;
26 }
冒泡排序
2、快速排序
原理说明：
（1）从序列中挑出一个元素，作为"基准"；
（2）把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区操作；
（3）对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
代码实现：
1 #include 2
3 int part(int *A,int left,int right)
4 {
5 int pivot=left;
6 int index=left+1;
7 int tmp=0;
8 for(int i=index;i)
9 {
10 if(A[i]A[pivot])
11 {
12 tmp=A[i];
13 A[i]=A[index];
14 A[index]=tmp;
15 ++index;
16 }
17 }
18 tmp=A[pivot];
19 A[pivot]=A[index-1];
20 A[index-1]=tmp;
21 return index-1;
22 }
23
24 void quickSort(int *A,int left,int right)
25 {
26 int pivotIndex;
27 if(leftright)
28 {
29 pivotIndex=part(A,left,right);
30 quickSort(A,left,pivotIndex-1);
31 quickSort(A,pivotIndex+1,right);
32 }
33 }
34
35 int main()
36 {
37 int A[]={5,2,9,4,7,6,1,3,8};
38 int n=sizeof(A)/sizeof(int);
39 quickSort(A,0,n-1);
40 for(int i=0;i)
41 {
42 printf("%d ",A[i]);
43 }
44 return 0;
45 }
快速排序
第二类：插入排序
1、简单插入排序
原理说明：
（1）从第一个元素开始，该元素可以认为已经被排序；
（2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
（5）将新元素插入到该位置后；
（6）重复步骤2~5。
代码实现：
1 #include 2
3 int main()
4 {
5 int A[]={6,5,3,1,8,7,2,4};
6 int n=sizeof(A)/sizeof(int);
7 //从小到大
8 int i,j,tmp;
9 for(i=1;i)
10 {
11 tmp=A[i];
12 for(j=i-1;j>=0 && tmp)
13 {
14 A[j+1]=A[j];
15 }
16 A[j+1]=tmp;
17 }
18 for(i=0;i)
19 {
20 printf("%d ", A[i]);
21 }
22 return 0;
23 }
简单插入排序
2、希尔排序
原理说明：
（1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
（2）插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
代码实现：
1 #include 2
3 void shellSort(int *A,int n)
4 {
5 int step=n/2;
6 int i,j,tmp;
7 while(step>=1)
8 {
9 for(i=step;i)
10 {
11 tmp=A[i];
12 for(j=i-step;j>=0 && A[j]>tmp;j-=step)
13 {
14 A[j+step]=A[j];
15 }
16 A[j+step]=tmp;
17 }
18 step/=2;
19 }
20 }
21
22 int main()
23 {
24 int A[]={6,5,3,1,8,7,2,4};
25 int n=sizeof(A)/sizeof(int);
26 shellSort(A,n);
27 for(int i=0;i)
28 {
29 printf("%d ",A[i]);
30 }
31 return 0;
32 }
希尔排序
第三类：选择排序
1、简单选择排序
原理说明：
（1）初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；
（2）再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾；
（3）以此类推，直到所有元素均排序完毕。
代码实现：
1 #include 2
3 int main()
4 {
5 int A[]={6,5,3,1,8,7,2,4};
6 int n=sizeof(A)/sizeof(int);
7 //从小到大
8 int index,tmp;
9 for(int i=0;i1;i++)
10 {
11 index=i;
12 for(int j=i+1;j)
13 {
14 if(A[j]A[index])
15 {
16 index=j;
17 }
18 }
19 tmp=A[i];
20 A[i]=A[index];
21 A[index]=tmp;
22 }
23 for(int i=0;i)
24 {
25 printf("%d ",A[i]);
26 }
27 return 0;
28 }
简单选择排序
2、堆排序
原理说明：
堆排序是指利用堆这种数据结构所设计的一种选择排序算法，堆是一种近似完全二叉树的结构。
（1）由输入的无序数组构造一个最大堆，作为初始的无序区；
（2）把堆顶元素（最大值）和堆尾元素互换；
（3）把堆（无序区）的尺寸缩小1，并从新的堆顶元素开始进行堆调整；
（4）重复步骤2，直到堆的尺寸为1。
代码实现：
1 #include 2
3 //堆调整
4 void heapAdjust(int *A,int i,int size)
5 {
6 int leftChild=2*i+1;
7 int rightChild=2*i+2;
8 int root=i;
9 if(leftChildA[root])
10 {
11 root=leftChild;
12 }
13 if(rightChildA[root])
14 {
15 root=rightChild;
16 }
17 int tmp;
18 if(root!=i)
19 {
20 tmp=A[i];
21 A[i]=A[root];
22 A[root]=tmp;
23 heapAdjust(A,root,size);
24 }
25 }
26
27 void heapSort(int *A,int size)
28 {
29 //建立堆
30 for(int i=size/2-1;i>=0;i--)
31 {
32 heapAdjust(A,i,size);
33 }
34 int tmp;
35 for(int i=size-1;i>0;i--)
36 {
37 tmp=A[0];
38 A[0]=A[i];
39 A[i]=tmp;
40 heapAdjust(A,0,i);
41 }
42 }
43
44 int main()
45 {
46 int A[]={6,5,3,1,8,7,2,4};
47 int n=sizeof(A)/sizeof(int);
48 heapSort(A,n);
49 for(int i=0;i)
50 {
51 printf("%d ",A[i]);
52 }
53 return 0;
54 }
堆排序
第四类：归并排序
1、二路归并排序
原理说明：
递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。
（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
（4）重复步骤3直到某一指针到达序列尾；
（5）将另一序列剩下的所有元素直接复制到合并序列尾。
代码实现：
1 #include 2 #include 3
4 //合并两个已排好序的数组
5 void merge(int *A,int left,int mid,int right)
6 {
7 int len=right-left+1;
8 int *tmp=(int*)malloc(sizeof(int)*len);
9 int i=left;
10 int j=mid+1;
11 int index=0;
12 while(iright)
13 {
14 tmp[index++]=A[i]];
15 }
16 while(imid)
17 {
18 tmp[index++]=A[i++];
19 }
20 while(jright)
21 {
22 tmp[index++]=A[j++];
23 }
24 for(int k=0;k)
25 {
26 A[left++]=tmp[k];
27 }
28 free(tmp);
29 }
30
31 void mergeSort(int *A,int left,int right)
32 {
33 int mid;
34 if(leftright)
35 {
36 mid=(left+right)/2;
37 mergeSort(A,left,mid);
38 mergeSort(A,mid+1,right);
39 merge(A,left,mid,right);
40 }
41 }
42
43 int main()
44 {
45 int A[]={6,5,3,1,8,7,2,4};
46 int n=sizeof(A)/sizeof(int);
47 mergeSort(A,0,n-1);
48 for(int i=0;i)
49 {
50 printf("%d ",A[i]);
51 }
52 return 0;
53 }
二路归并排序
附：在我们做笔试的过程中，经常会用到全排与组排的算法思想，所以在这里也一并的整理出来。
1、全排算法
代码实现：
1 #include 2 #include 3
4 void swap(int *p1,int *p2)
5 {
6 int t=*p1;
7 *p1=*p2;
8 *p2=t;
9 }
10
11 void permutation(int a[],int index,int size)
12 {
13 if(index==size)
14 {
15 for(int i=0;i)
16 printf("%d ",a[i]);
17 printf("\n");
18 }
19 else
20 {
21 for(int j=index;j)
22 {
23 swap(&a[j],&a[index]);
24 permutation(a,index+1,size);//此处用到递归思想
25 swap(&a[j],&a[index]);
26 }
27 }
28 }
29
30 int main()
31 {
32 int n;
33 scanf("%d",&n);
34 int *a=(int*)malloc(sizeof(int)*n);
35 for(int i=0;i)
36 a[i]=i+1;
37 permutation(a,0,n);
38 free(a);
39 return 0;
40 }
全排算法
输入：
4
输出：
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
3 1 2 4
3 1 4 2
3 4 1 2
3 4 2 1
4 2 3 1
4 2 1 3
4 3 2 1
4 3 1 2
4 1 3 2
4 1 2 3
全排输出
2、组排算法
代码实现：
1 #include 2 #include 3
4 void combine(int n,int m,int a[],int b[],const int M)
5 {
6 for(int j=n;j>=m;j--)
7 {
8 b[m-1]=j-1;
9 if(m>1)combine(j-1,m-1,a,b,M);//用到了递归思想
10 else
11 {
12 for(int i=M-1;i>=0;i--)
13 {
14 printf("%d ",a[b[i]]);
15 }
16 printf("\n");
17 }
18 }
19 }
20
21 int main()
22 {
23 int n,m;
24 scanf("%d%d",&n,&m);
25 int *a=(int*)malloc(sizeof(int)*n);
26 int *b=(int*)malloc(sizeof(int)*m);
27 for(int i=0;i)
28 a[i]=i+1;
29 const int M=m;
30 combine(n,m,a,b,M);
31 free(a);
32 free(b);
33 return 0;
34 }
组排算法
输入：
4 3
输出：
组排输出
后记：欢迎各路大神批评与指正！
常见的排序算法总结
标签：二叉树 gif 简单选择排序 ide i++ free root inf adjust
原文地址：https://www.cnblogs.com/gcl0909031172/p/9744901.html