快速排序
设置个关键字，将大的放在它后面，小的放在前面，分成两个子表，并且重复上述过程，直到每一个子表只有一个记录为止
const quickSort = function(arr){
if(arr.length <= 0)return arr;
const index = Math.floor(arr.length / 2);
const key = arr.splice(index, 1)[0];
const left = [];
const right = [];
for(let i = 0; i < arr.length; i++){
if(arr[i] < key)left.push(arr[i]);
else right.push(arr[i]);
}
return quickSort(left).concat([key], quickSort(right));
}
console.log(quickSort([2, 5, 1, 9, 6, 1, 4]));
console.log(['Jan', 'March', 'April', 'June'].splice(1, 1, 'Feb'));1.不稳定排序
2.多用于顺序结构
3.时间复杂度O(nlog2 n)。 空间复杂度为O(log2 n), 最坏O(n).
最坏情况是逆序，或基本有序（顺序）
直接插入排序
这里采用的是从后向前的比较方式，（从前向后其实也可以）
有点像打牌，抽牌，然后选择地方放好
function insertion(array) {
checkArray(array);
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
swap(array, j, j + 1);
}
return array;
}1.稳定排序
2.适用于顺序表和链表
3.时间复杂度为O(n^2) 空间复杂度为O(1),只需要一个r[0]
优化插入排序
变量覆盖
const insertSort = (arr, start = 0, end) => {
end = end || arr.length;
for(let i = start; i < end; i++) {
let e = arr[i];
let j;
for(j = i; j > start && arr[j - 1] > e; j --)
arr[j] = arr[j-1];
arr[j] = e;
}
return;
}折半插入排序
其实就是直接插入排序引入了折半的思想
//算法8.2 折半插入排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{
int key;
char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{
ElemType *r; //存储空间的基地址
int length; //顺序表长度
}SqList; //顺序表
void BInsertSort(SqList &L){
//对顺序表L做折半插入排序
int i,j,low,high,m;
for(i=2;i<=L.length;++i)
{
L.r[0]=L.r[i]; //将待插入的记录暂存到监视哨中
low=1; high=i-1; //置查找区间初值
while(low<=high)
{ //在r[low..high]中折半查找插入的位置
m=(low+high)/2; //折半
if(L.r[0].key<L.r[m].key) high=m-1; //插入点在前一子表
else low=m+1; //插入点在后一子表
}//while
for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //记录后移
L.r[high+1]=L.r[0]; //将r[0]即原r[i]，插入到正确位置
} //for
} //BInsertSort
void Create_Sq(SqList &L)
{
int i,n;
cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;
cin>>n; //输入个数
cout<<"请输入待排序的数据：\n";
while(n>MAXSIZE)
{
cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;
cin>>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i].key<<endl;
}
void main()
{
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
BInsertSort(L);
cout<<"排序后的结果为："<<endl;
show(L);
}1.稳定排序
2.仅适用于顺序表
3.时间复杂度为O(n^2)，但是平均性能>直接插入。 空间复杂度为O(1),只需要一个r[0]
希尔排序
通过分组进行大浮动跳跃性排序，并且分组的形式是以设定的增量为基准
//算法8.3 希尔排序
#include
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{
int key;
char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{
ElemType *r; //存储空间的基地址
int length; //顺序表长度
}SqList; //顺序表类型
void ShellInsert(SqList &L,int dk)
{
//对顺序表L做一趟增量是dk的希尔插入排序
int i,j;
for(i=dk+1;i<=L.length;++i)
if(L.r[i].key0&& L.r[0].key>n; //输入个数
cout<<"请输入待排序的数据：\n";
while(n>MAXSIZE)
{
cout<<"个数超过上限，不能超过"<>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<>t;
for(i=0;i>dt[i];
}
ShellSort(L,dt,t);
cout<<"排序后的结果为："< 1.不稳定排序
2.仅适用于顺序表
3.时间复杂度取决于增量的决定，最少可以减少到n(log2 n)^2, n^3/2等。 空间复杂度为O(1),只需要一个r[0]
对于增量的选取很重要，希尔自带的增量设定为 {N/2, (N / 2)/2, …, 1} ，叫做希尔增量，常用但是效果并不拔群，其余的有 Hibbard：{1, 3, …, 2^k-1}，Sedgewick：{1, 5, 19, 41, 109…} 等
字典排序
实现“ 1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1 ”的序列排序方法
代码实现如下
#include
#define swap(a,b) {int temp=a;a=b;b=temp;} //交换a，b值
void sort(int arr[],int start,int end)//冒泡排序，从start到end的排序，使用时注意是数组的下标，如数组下标0-3排序，sort（arr,0,3）
{
int i,j;
for(i=0;i<=end-start;i++)
{
for(j=start;j<=end-i-1;j++)
{
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1]);
}
}
}
void permutation(int arr[],int n) //字典排序
{
int num=1,i=0,j=0,j1=0,k=0,a,b;
for(i=1;i<=n;i++)//算出需要执行的次数，即全排列的次数，共n！种排法
{
num=num*i;
}
sort(arr,0,n-1);//先对数组进行一次按从小到大排列排序
for(k=num;k>0;k--) //进行num次循环
{
for(i=0;i0;j--)
{
if(arr[j-1]=0;j1--)
{
if(arr[j1]>arr[a]) //这是字典排序第二步，获取arr[b]的值
{
b=j1;
break;
}
}
swap(arr[a],arr[b]); //这是第三步
sort(arr,a+1,n-1); //这是第四步
}
}
int main()
{
int arr[]={1,2,4,3};
permutation(arr,4);
return 0;
} 总结得出字典排序算法四步法：
字典排序：
第一步：从右至左找第一个左邻小于右邻的数，记下位置i，值list[a]
第二部：从右边往左找第一个右边大于list[a]的第一个值，记下位置j，值list[b]
第三步：交换list[a]和list[b]的值
第四步：将i以后的元素重新按从小到大的顺序排列
举例：125643的下一个字典序列
第一步：右边值大于左边的3<4,4<6,6>5,则i=2，list[a]=5
第二步：从右往左找出第一个右边大于list[a]=5的值，找到6>5,j=3;list[b]=6;
第三步：交换list[a]和list[b]的值，序列125643->126543
第四步：将位置2以后的元素重新排序,126543->126345;
结束： 126345即125643的下一个序列
简单选择排序
选择关键字储存最小的记录：和表中的记录进行一一对比，选出最小记录放在开头，接着从第二个记录继续开始
//算法8.6 简单选择排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{
int key;
char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{
ElemType *r; //存储空间的基地址
int length; //顺序表长度
}SqList; //顺序表类型
void SelectSort(SqList &L)
{
//对顺序表L做简单选择排序
int i,j,k;
ElemType t;
for(i=1;i<L.length;++i)
{ //在L.r[i..L.length] 中选择关键字最小的记录
k=i;
for(j=i+1;j<=L.length;++j)
if(L.r[j].key<L.r[k].key) k=j; //k指向此趟排序中关键字最小的记录
if(k!=i) {t=L.r[i];L.r[i]=L.r[k];L.r[k]=t;} //交换r[i]与r[k]
} //for
} // SelectSort
void Create_Sq(SqList &L)
{
int i,n;
cout<<"请输入数据个数，不超过"<<MAXSIZE<<"个。"<<endl;
cin>>n; //输入个数
cout<<"请输入待排序的数据:\n";
while(n>MAXSIZE)
{
cout<<"个数超过上限，不能超过"<<MAXSIZE<<"，请重新输入"<<endl;
cin>>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i].key<<endl;
}
void main()
{
SqList L;
L.r=new ElemType[MAXSIZE+1];
L.length=0;
Create_Sq(L);
SelectSort(L);
cout<<"排序后的结果为："<<endl;
show(L);
}1.稳定排序，但如果是采用“交换记录”，则会导致不稳定现象
2.顺序，链式皆可以使用
3.时间复杂度O( n^2 ),比直接插入快。 空间复杂度为O(l1).
基数排序
使用的大致思路是：根据关键字进行分类，再次排序，在分类，在排序，以此类推直至完成结果
如扑克牌中根据分13类，排序，再根据花色分类，再排序； 对百位数排序，先根据个位分类，排，再根据十位分类，排，再根据百位分类，排
//算法8.12 基数排序
#include
using namespace std;
#include
#include
#include
#define MAXNUM_KEY 8 //关键字项数的最大值
#define RADIX 10 //关键字基数，此时是十进制整数的基数
#define MAX_SPACE 10000
typedef char KeysType; //定义关键字类型为字符型
typedef int InfoType; //定义其它数据项的类型
typedef struct
{
KeysType keys[MAXNUM_KEY]; //关键字
InfoType otheritems; //其他数据项
int next;
}SLCell; //静态链表的结点类型
typedef struct
{
SLCell r[MAX_SPACE]; //静态链表的可利用空间，r[0]为头结点
int keynum; //记录的当前关键字个数
int recnum; //静态链表的当前长度
}SLList; //静态链表类型
typedef int ArrType[RADIX]; //指针数组类型
void InitList(SLList *L)
{
//初始化静态链表L（把数组D中的数据存于L中）
char c[MAXNUM_KEY],c1[MAXNUM_KEY];
int i,j,n,max; //max为关键字的最大值
max=-10000;
cout<<"请输入数据个数，不超过"<>n;
while(n>MAX_SPACE)
{
cout<<"您输入的个数超过上限，请重新输入，不超过"<>n;
}
int *D=new int[n];
cout<<"请输入"<>D[i];
if(max=0;j--)
cout< 1.稳定排序
2.适用于顺序表和链表,一般采用静态链式
3.时间复杂度为O(d(n+rd))/O(n) 空间复杂度为O(n+rd)
4.但是它的使用有严格要求，必须知道各级关键字的主次关系和各级关键字的取值范围
冒泡排序
将关键字大的记录“下沉”,与小的记录进行交换
//算法8.4 冒泡排序
#include
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{
int key;
char *otherinfo;
}ElemType;
//顺序表的存储结构
typedef struct
{
ElemType *r; //存储空间的基地址
int length; //顺序表长度
}SqList; //顺序表类型
void BubbleSort(SqList &L)
{
//对顺序表L做冒泡排序
int m,j,flag;
ElemType t;
m=L.length-1; flag=1; //flag用来标记某一趟排序是否发生交换
while((m>0)&&(flag==1))
{
flag=0; //flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
for(j=1;j<=m;j++)
if(L.r[j].key>L.r[j+1].key)
{
flag=1; //flag置为1，表示本趟排序发生了交换
t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t; //交换前后两个记录
} //if
--m;
} //while
} //BubbleSort
void Create_Sq(SqList &L)
{
int i,n;
cout<<"请输入数据个数，不超过"<>n; //输入个数
cout<<"请输入待排序的数据:\n";
while(n>MAXSIZE)
{
cout<<"个数超过上限，不能超过"<>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout< 1.稳定排序
2.顺序链式都适用
3.时间复杂度O(n^2)。 空间复杂度为O(1).
归并排序
将相邻的两个记录（序列）排序，并成一个有序序列，并继续上述操作
//算法8.11 归并排序
#include
using namespace std;
#define MAXSIZE 20 //顺序表的最大长度
typedef struct
{
int key;
char *otherinfo;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cout<<"请输入数据个数，不超过"<>n; //输入个数
cout<<"请输入待排序的数据:\n";
while(n>MAXSIZE)
{
cout<<"个数超过上限，不能超过"<>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
//用算法8.10 相邻两个有序子序列的归并
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
//将有序表R[low..mid]和R[mid+1..high]归并为有序表T[low..high]
int i,j,k;
i=low; j=mid+1;k=low;
while(i<=mid&&j<=high)
{
//将R中记录由小到大地并入T中
if(R[i].key<=R[j].key) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(i<=mid) //将剩余的R[low..mid]复制到T中
T[k++]=R[i++];
while(j<=high) //将剩余的R[j.high]复制到T中
T[k++]=R[j++];
}//Merge
void MSort(RedType R[],RedType T[],int low,int high)
{
//R[low..high]归并排序后放入T[low..high]中
int mid;
RedType *S=new RedType[MAXSIZE];
if(low==high) T[low]=R[low]; //序列长度为1，直接结束
else
{
mid=(low+high)/2; //将当前序列一分为二，求出分裂点mid
MSort(R,S,low,mid); //对子序列R[low..mid] 递归归并排序，结果放入S[low..mid]
MSort(R,S,mid+1,high); //对子序列R[mid+1..high] 递归归并排序，结果放入S[mid+1..high]
Merge(S,T,low,mid,high); //将S[low..mid]和S [mid+1..high]归并到T[low..high]
}//else
}// MSort
void MergeSort(SqList &L)
{
//对顺序表L做归并排序
MSort(L.r,L.r,1,L.length);
}//MergeSort
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout< 1.稳定排序
2.顺序，链式皆可以使用
3.时间复杂度O( nlog2 n ), 空间复杂度为O(n).
