10.1 内部排序与外部排序
内部排序：待排序的所有记录全部存放在计算机内存中，整个排序过程不需要访问外存
外部排序：等待排序的记录数量很大，以至于整个序列的排序过程不可能在内存中完成，在排序过程中还需要对外存进行访问
性能指标
-
时间开销
-
空间开销
-
算法稳定性：存在多个具有相同的关键字值的记录，若经过排序操作，这些记录的相对先后次序仍然保持不变
10.2 插入排序
10.2.1 直接插入排序
算法思想：将待排记录看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次逐个地插入到左边的有序区中（按关键字大小确定位置），以构成新的有序区，直到全部记录都排好序
1 void InsertSort( SqList & L )
2 { //对顺序表L作直接插入排序（升序）。
3 int i, j;
4 for( i=2; i<=L.length; ++i ) // 排序趟数
5 if LT( L.r[i].key, L.r[i-1].key ) // 当r[i]小时, 需要暂存、移动、插入
6 { L.r[0] = L.r[i]; // 必须先用r[0]暂存r[i]的值
7 for(j=i-1; LT( L.r[0].key, L.r[j].key ); --j) L.r[j+1] = L.r[j]; //比较，右移（找到插入位置）
8 L.r[j+1] = L.r[0]; //在已经移好的位置处插入
9 }
10 }
空间性能：需要设置一个大小为一个记录r[0]的辅助空间
时间性能：
-
若初始时n 个元素的关键字递增有序，这是最好情况。此时，每趟排序中，仅需进行一次关键字的比较：总的“比较”次数为 n-1 【最少】 总的“移动”的次数为0
-
若初始时n 个关键字递减有序，这是最坏情况。每趟排序中，需要比较的次数分别是: (1+1),(2+1),…,(n-1+1) ，总的“比较”次数为 (n+2)(n-1) /2 【最多】 总的“移动”次数为: 1+2+…+n-1
算法的时间复杂度：O(n^2)
10.2.2 折半插入排序
在直接插入排序的基础上，对有序区的插入位置的查找，可以采用折半查找的方法
1 void BInsertSort ( SqList &L )
2 { for ( i=2; i<=L.length; ++i )
3 { L.r[0] = L.r[i]; //将 L.r[i] 暂存到 L.r[0]
4 //在 L.r[1 ] ... L.r[i-1]中折半查找插入位置
5 low = 1; high = i-1;
6 while (low<=high)
7 { m = (low+high)/2; //折半查找
8 if(L.r[0].key<L.r[m].key)high=m-1; //插入点在低半区
9 else low = m+1; //插入点在高半区
10 } //while循环结束时，插入点 m=high+1 找到
11 for ( j=i-1; j>=high+1; --j ) L.r[j+1] = L.r[j];
12 //将 j=high+1 ~ j=i-1（先）的所有记录右移
13 L.r[high+1] = L.r[0]; //在插入位置插入
14 }//for
15 }
10.2.3 希尔排序
算法思想
-
首先，取一个整数d1作为第一个增量(d1一般 取全部记录数的一半)，把全部记录分组。所有距离为整数d1的倍数的记录都视作同一组。之后，在各个组内都都进行直接插入排序。
-
然后, 取第二个增量d2 (d2的值一般取d1的一半)重复上述的分组和直接插入排序，
。。。
-
直到所取的增量dt=1 (dt<…<d2<d1)——此时，对所有记录（都在同一组中）进行直接插入排序。
-
至此，希尔排序完成。
1 void ShellInsert(SqList &L, int dk)
2 { // 只对顺序表L做一趟希尔排序。
3 // 注意前后记录的位置的增量都是dk;
4 for ( i=dk+1; i<=L.length; ++i ) //dk+1是第1个子序列的第2个元素的下标
5 if LT( L.r[i].key, L.r[i-dk].key)//将L.r[i]用直接插入法插入有序增量子表
6 { L.r[0]=L.r[i]; //在0位暂存
7 for( j=i-dk; j>0&<( L.r[0].key, L.r[j].key ); j-=dk )
8 L.r[j+dk]=L.r[j]; //记录后移，查找到插入位置时退出循环
9 L.r[j+dk]=L.r[0]; //插入
10 }
11 }
12 void ShellSort( SqList &L, int dlta[ ], int t )
13 { //按增量数组的dlta[0] ...dlta[t-1]增量，对表L作希尔排序。
14 for(int k=0; k < t; ++k )
15 ShellInsert( L, dlta[k] ); //共有t趟希尔排序
16 }
10.3 快速排序
10.3.1 冒泡排序
算法思想
-
首先将第一个记录的关键字与相邻的第二个记录的关键字相比，若为逆序(即L.r[1].key>L.r[2].key)，则将两记录交换，
-
然后比较第二个记录与相邻的第三个记录的关键字，若为逆序，则将两记录交换。
-
依次类推，直到第n-1个记录和相邻的第n个记录的关键字进行比较，若为逆序，则将两记录交换——到此为止，此时的结果是关键字最大的记录被交换到最后一个位置即第n个记录的位置上。
-
上述过程称为第一趟起泡排序；
-
之后进行第二趟起泡排序，对前n-1个记录进行同样的操作，其结果是关键字次最大的记录被交换到第n-1个记录的位置上。
-
以此类推，经过最后一趟起泡排序，可完成顺序表的升序排序
1 #include<iostream>
2 using namespace std ;
3 void bubble( int a[ ] , int n)
4 { int t; int flag = 0;
5 for(int i=1; i<=n-1; i++) // n个数, 需进行n-1趟比较
6 { flag = 0;
7 for(int j=1; j<=n-i; j++) // 完成第i 趟要进行n-i次比较
8 if (a[j-1]>a[j]) { t=a[j-1]; a[j-1]=a[j]; a[j]=t; flag = 1; }
9 if (flag == 0) break; //结束外部的for循环
10 }
11 }
12
13 void main()
14 { int a[10]={48, 62, 35, 77, 55, 14, 35,98, 22,40};
15 bubble(a, 10);
16 cout<<"the sorted numbers :\n";
17 for( int i=0; i<10; i++ ) cout<<a[i]<<" ";
18 cout<<endl;
19 }
最好情况（从小到大，正序）：
-
比较次数：n-1
-
移动次数：0
-
时间复杂度为O(n)
在平均情况下，起泡排序的时间复杂度与最坏情况同数量级O(n^2)
-
起泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元
-
起泡排序是一种稳定的排序方法
10.3.2 快速排序
算法思想
-
取待排序列中某个记录的关键字(通常选第一个记录的)作为枢轴，通过一趟快速排序将待排序列中的记录分割成独立的两部分，其中: 左边部分的所有记录的关键字都小于等于这个枢轴，而右边部分的所有记录的关键字都大于等于这个枢轴。即通过一趟快速排序，该枢轴的最后位置成为分界线，将序列分割成两个子序列。这个过程也称为一次划分 。
-
然后再按此方法对两个子序列分别进行快速排序，以此达到整个序列变成有序序列。
-
整个排序过程是递归进行。
1 int Partition (SqList &L, int low, int high)
2 { //使枢轴最后位置之前(后)的均不大(小)于它,并返回枢轴最后位置。pivotkey = L.r[low].key; //枢轴记录的关键字，确定枢轴记录
3 while (low<high) //从表的两端交替地向中间扫描,
4 { while ( low<high && L.r[high].key >= pivotkey ) --high;
5 L.r[low]←→L.r[high]; //与右边比枢轴记录小的记录互换位置
6 while (low<high && L.[low].key <= pivotkey ) ++low;
7 L.r[low]←→L.r[high]; //与左边比枢轴记录大的记录互换位置
8 }
9 return low; // 返回枢轴记录所在位置
10 }
优化的一趟快速排序（一次划分）的算法
1 int Partition (SqList &L, int low, int high)
2 {
3 L.r[0] = L.r[low]; //用0下标位置保存枢轴记录,
4 pivotkey = L.r[low].key; //确定枢轴，枢轴记录的关键字
5 while (low<high)
6 { while (low<high && L.r[high].key>=pivotkey ) --high;
7 L.r[low] = L.r[high]; //比枢轴小的记录移到低端
8 while (low<high && L.r[low].key<=pivotkey ) ++low;
9 L.r[high] = L.r[low] ; //比枢轴大的记录移到高端
10 }
11 L.r[low] = L.r[0] ; //找到枢轴记录位置low, 并恢复枢轴记录的值
12 return low; //返回枢轴记录所在位置
13 }
快速排序（递归算法）
1 void QSort (SqList &L, int low, int high)
2 {
3 if (low<high)
4 { pivotlocation = Partition (L, low, high) ;
5 QSort (L, low, pivotlocation-1);
6 QSort (L, pivotlocation+1, high);
7 }
8 }
快速排序的平均时间：knlnn，其中 k为常数因子
-
快速排序需要栈空间来实现递归。最坏情况下，栈的深度为n
10.4 选择排序
算法思想
-
在第一趟选择排序时，在n个记录的表r[0] … r[n-1]中找到关键字最小的记录，若它与r[0]不相等，则将它与r[0]对调。则此时，表中的r[0]的关键字最小—即通过比较，最先要把关键字最小的记录选出来，并把它的位置安排在r[0]。
-
在第二趟选择排序时，只需要在剩余的n-1个记录的表r[1] … r[n-1]中找到其关键字最小的记录，若它与r[1]不相等，则将它与r[1]对调。此时，表中的r[1]的关键字是整个的次最小。
-
同理，可处理后续的
-
在之后的每趟排序，在右边所面对的待排序列中选出关键字最小的记录，添加到左边已经有序的序列中
1 void SelectSort (Sqlist &L, int n)
2 { for (i=0; i<L.length-1; i++) //一共有L.length-1趟比较
3 { k=i;
4 for ( j=i+1; j<L.length; j++)
5 if ( L.r[j].key < L.r[k].key ) k=j;
6 if (k!=i) { temp=L.r[i]; L.r[i]=L.r[k]; L.r[k]=temp; }
7 }
8 }
标签：记录,int,枢轴,关键字,算法,low,排序 From： https://www.cnblogs.com/eecsCodeStar/p/16981410.html