新人部落客不易，希望看完點贊
/**
*autor：旋塵
*time:2020.7.20
*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef int ElemType;
typedef struct
{
ElemType r[MAXSIZE+1];//r[0]是空的，或者被暫用像temp一樣當做監視哨
int length;//具體元素個數
}SortList;
int Menu()
{
int check_number;
do{
system("cls"); /*運作前清屏,把選擇清掉*/
printf("\t************排序表系統*************\n");
printf("\t*| 1. 建立排序表 *\n");
printf("\t*| 2. 直接插入排序 *\n");
printf("\t*| 3. 折半插入排序 *\n");
printf("\t*| 4. 二路折半插入排序 *\n");
printf("\t*| 5. 希爾排序 *\n");
printf("\t*| 6. 起泡排序 *\n");
printf("\t*| 7. 快速排序 *\n");
printf("\t*| 8. 簡單選擇排序 *\n");
printf("\t*| 9. 非遞歸歸并排序 *\n");
printf("\t*| 10. 計數排序 *\n");
printf("\t*| 11. 列印排序表 *\n");
printf("\t*| 12. 退出系統 *\n");
printf("請輸入選擇(1-12):");
scanf("%d",&check_number);
if(check_number<1||check_number>12)
{
printf("錯誤選擇\n");
system("pause");
}
}while(check_number<0||check_number>12);
return check_number;
}
void createList(SortList *L)
{
int i=0;ElemType x;
printf("請輸入需要排序的數，輸入-1結束\n");
scanf("%d",&x);
while(x!=-1)
{
/*課本代碼219，有錯誤
if(i>MAXSIZE) 先越界再退出循環
{--i;break;}
L->r[++i]=x;
if(i==5)//當時MAXSIZE=4，是以r[5]越界了
{
printf("異常%d\n",L->r[5]);
}
scanf("%d",&x);*/
if(i==MAXSIZE)
{break;}
L->r[++i]=x;
scanf("%d",&x);
}
L->length=i;
}
void printList(SortList *L)
{
int i;
for(i=1;i<=L->length;i++)
{
printf("%5d",i);
}
printf("\n");
for(i=1;i<=L->length;i++)
{
printf("%5d",L->r[i]);
}
printf("\n");
}
//直接插入排序
//直接插入排序，即從第二個元素開始，每個元素與前面一個比較，若大于前面那個就不動，若小于那個，先用r[0]存它
//然後從r[i-1]到r[1]邊後移邊比較，當找到r[0]大于那個位置就插進去那個位置前面
void insertSort(SortList *L)
{
int i,j;
for(i=2;i<=L->length;i++)
{
if(L->r[i]<L->r[i-1])//小于它後面那一位
{
L->r[0]=L->r[i];//暫存它
for(j=i-1;L->r[0]<L->r[j];j--)//找到那個數應該插入位置之前，把比它大那些數後移
{
L->r[j+1]=L->r[j];
}
L->r[j+1]=L->r[0];//插入應該插入位置
}
}
printList(L);
}
//折半插入排序算法：即從i=2到結尾，每個元素用折半算法插入它前面的序列
void biInsertSort(SortList *L)
{
int i,j,low,high,mid;
for(i=2;i<L->length;i++)
{
L->r[0]=L->r[i];
low=1,high=i-1;
while(low<=high)//找到該插入地方
{
mid=(low+high)/2;
if(L->r[0]<L->r[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
for(j=i-1;j>=high+1;--j)
{
L->r[j+1]=L->r[j];//該插入的那個位置前面元素後移
}
L->r[high+1]=L->r[0];//插入
}
printList(L);
}
//2路插入排序不了解就看課本，有圖，是折半插入排序進化版
void twoInsertSort(SortList *L)
{
int i,j,final,first,low,high,mid;
ElemType d[L->length+1];//課本用指針
first=L->length+1,final=1;
d[1]=L->r[1];
for(i=2;i<=L->length;i++)//排序每個元素
{
if(L->r[i]>=d[1])//從前面排
{
low=1,high=final;
while(low<=high)
{
mid=(low+high)/2;
if(L->r[i]<d[mid])
{
high=mid-1;
}
else{low=mid+1;}
}
for(j=final;j>=low;--j)//右移
{
d[j+1]=d[j];
}
d[low]=L->r[i];
final++;
}
else
{
low=first;high=L->length;
while(low<=high)
{
mid=(low+high)/2;
if(L->r[i]<d[mid])
{
high=mid-1;
}
else{low=mid+1;}
}
for(j=first;j<=high;j++)//左移
{
d[j-1]=d[j];
}
d[high]=L->r[i];
first--;
}
}
i=1;//将d記錄回到r
for(j=first;j<=L->length;j++)
{
L->r[i++]=d[j];
}
for(j=1;j<=final;j++)
{
L->r[i++]=d[j];
}
printList(L);
}
//希爾排序，即直接插入排序進化版，沒思路印象的話看b站收藏的資料結構的課，分别按照增量數組進行排序
void shellSort(SortList *L,int d[],int t)//d為增量序列，t為增量數組裡面的數
{
int i,j,k;
for(k=0;k<t;k++)//增量序列個數多少就排序幾次
{
for(i=d[k]+1;i<=L->length;i++)
{
if(L->r[i]<L->r[i-d[k]])//像直接插入排序法一樣，從第二個元素開始
{
L->r[0]=L->r[i];//暫存元素
for(j=i-d[k];j>0&&L->r[0]<L->r[j];j-=d[k])
{
L->r[j+d[k]]=L->r[j];//右移
}
L->r[j+d[k]]=L->r[0];//插入合适位置
}
}
}
printList(L);
}
/交換排序
void bubbleSort(SortList *L)// 起/冒泡排序
{
int i,j,flag=1;
ElemType temp;
for(i=1;flag&&i<=L->length;i++)
{
for(flag=0,j=1;j<L->length-i;j++)
{
if(L->r[j]>L->r[j+1])
{
temp=L->r[j];
L->r[j]=L->r[j+1];
L->r[j+1]=temp;
flag=1;
}
}
}
printList(L);
}
//快速排序，忘了就看看課本那張圖
void hoareSort(SortList *L,int low,int high)//讓處于low下标的元素在low---high之間往返比較，找到屬于自己的位置
{
int i,j;
if(low<high)
{
i=low;j=high;//讓下标是i的那個元素不停，但它在左邊向右邊j在的地方向左比較，直到遇到比它小就停下來交換位置
//再在右邊向左邊i在的地方向右比較，直到遇到比它比它大的元素就停下來交換位置，i=j就是它找到自己位置
L->r[0]=L->r[i];//暫存元素
while(i<j)
{
while(i<j&&L->r[j]>=L->r[0])//在左邊，，找到小于它的數才向右交換
{j--;}
L->r[i]=L->r[j];
//在右邊了，，，，找到小于等于它的數才向左交換交換👇
while(i<j&&L->r[i]<L->r[0])//上面是>=，下面是<沒有=因為都沒=的時候它遇到等于自己的數時會陷入死循環，
{i++;}
L->r[j]=L->r[i];
//不斷往返交換
}
//排完序後小的在它左邊，大于它的在它右邊，是以左邊的排完序還在左邊，右邊的排完序還在右邊，是以low,high遞歸時要改變
L->r[i]=L->r[0];
hoareSort(L,low,i-1);//讓自己左邊的第一個數排序
hoareSort(L,i+1,high);//讓自己右邊的第一個數排序
//不斷遞歸直到結束
}
}
選擇排序
//簡單選擇排序
void selectSort(SortList *L)//把最小數的坐标記錄下來，一個循環後放在未排序的隊列第一個，然後減小未排序數量1
{
int i,j,k;ElemType t;
for(i=1;i<L->length;i++)
{
for(k=i,j=i+1;j<=L->length;j++)
{
if(L->r[k]>L->r[j])
{k=j;}
}
if(k!=i)
{
t=L->r[k];L->r[k]=L->r[i];L->r[i]=t;
}
}
printList(L);
}
///歸并排序，思路：先分成許多小至1序列，再不斷合并排序、
//非遞歸歸并排序算法，遞歸的課本也有，思路差不多
void Msort(SortList *L,int b,int d)//将a[b]---a[b+d-1]的序列與a[b+d]----a[b+2d-1]序列排序
//b+2d-1可能越界，但會有限制
{
int i,j,k=0;ElemType t[2*d];//課本指針申請記憶體
i=b,j=b+d;
while(i<b+d&&j<=L->length&&j<b+2*d)//防止越界，讓兩部分按照大小存進t裡面,直到一個裡面沒有元素
{
if(L->r[i]<L->r[j])
{
t[k++]=L->r[i++];//i++不是++i
}
else
{
t[k++]=L->r[j++];
}
}
while(i<b+d&&i<=L->length)//第一部分元素沒存完,課本這裡沒限制越界
{
t[k++]=L->r[i++];
}
while(j<=L->length&&j<b+2*d)
{
t[k++]=L->r[j++];
}
for(i=b;i<b+2*d;i++)//指派
{
L->r[i]=t[i-b];
}
}
void mergeSort(SortList *L)//課本有筆記
{
int i,j;
for(i=1;i<=L->length;i++)
{
j=1;
while(j<L->length)
{
Msort(L,j,i);
j+=2*i;
}
}
printList(L);
}
/計數排序，思路很簡單，忘了看一下課本就行
void countSort(SortList *L)
{
SortList Q=*L;
int i,j;
ElemType c[L->length+1];
for(i=1;i<=L->length;i++)
{
c[i]=1;
}
for(i=1;i<L->length;i++)
{
for(j=i+1;j<=L->length;j++)//一個數大于序列裡多少個數它的位置就是那個數+1
{
if(Q.r[i]>Q.r[j])
{
c[i]++;
}
else
{
c[j]++;
}
}
}
for(i=1;i<=L->length;i++)
{
L->r[c[i]]=Q.r[i];//注意這裡Q不是指針，它複制了L，L改變，它不會改變
}
printList(L);
}
//基數排序概念思想了解了，是看b站視訊了解的但是課本相差太大，沒大，有問題看視訊即可
void quickSort(SortList *L)
{
hoareSort(L,1,L->length);
printList(L);
}
int main()
{
SortList L;
int t=3,d[3]={3,2,1};//希爾排序要
for(;;)
{
system("cls");
switch(Menu())
{
case 1: createList(&L);system("pause");continue;
case 2: insertSort(&L);system("pause");continue;
case 3: biInsertSort(&L);system("pause");continue;
case 4: twoInsertSort(&L);system("pause");continue;
case 5: shellSort(&L,d,t);system("pause");continue;
case 6: bubbleSort(&L);system("pause");continue;
case 7: quickSort(&L);system("pause");continue;
case 8: selectSort(&L);system("pause");continue;
case 9: mergeSort(&L);system("pause");continue;
case 10: countSort(&L);system("pause");continue;
case 11: printList(&L);system("pause");continue;
case 12: exit(0);
}
}
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)