問題描述?

1) 動態輸入一組數字序列;

2)實現直接插入排序、簡單選擇排序、冒泡排序、快速排序算法;

3)在主函數中，依次測試上述算法。

類型定義

#define MAX SIZE 100 typedef int KeyType ; typedef struct RecType { KeyType key ;/*關鍵字碼*/infoType otherinfo; /* 其他域*/ } RecType ; typedef struct SqList? { RecType R[MAX_ _SIZE+1]; //R[0]閑置或作哨兵單元int length ; }SqList ;

?解決方案

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define MAX_STACK 100 #define TRUE 0 #define FALSE -1 typedef int KeyType; typedef struct{KeyType key; }RedType; typedef struct{RedType r[MAXSIZE+1];int length; }SqList;void InitList_Sq(SqList &L) {int i;L.length = 0;printf("請依次輸入順序表值，以333結束:\n");for (i = 1; i < MAXSIZE; i++) {scanf("%d", &(L.r[i].key));L.length++;if(L.r[i].key==333)break;} }void straight_insert_sort(SqList &L) //直接插入排序 {int i, j ;for (i=2; i<=L.length; i++){ L.r[0]=L.r[i]; j=i-1; /* 設置哨兵 */while( L.r[i].key<L.r[j].key){ L.r[j+1]=L.r[j];j--;} /* 查找插入位置 */L.r[j+1]=L.r[0]; /* 插入到相應位置 */ } }void simple_selection_sort(SqList &L) //簡單選擇排序 { int m, n,k;for (m=1; m<L.length; m++){ k=m ; for (n=m+1; n<=L.length; n++)if (L.r[n].key<L.r[k].key) k=n;if (k!=m) /* 記錄交換 */{L.r[0]=L.r[m]; L.r[m]=L.r[k];L.r[k]=L.r[0];} } }void Bubble_Sort(SqList &L) //冒泡排序 { int j ,k , flag ;for (j=0; j<L.length-1; j++) /* 共有n-1趟排序 */{flag=TRUE ;for (k=1; k<L.length-j; k++) /* 一趟排序 */{ if (L.r[k+1].key<L.r[k].key){ flag=FALSE ;L.r[0]=L.r[k] ; L.r[k]=L.r[k+1] ; L.r[k+1]=L.r[0] ; }}if (flag==TRUE) break ;} }int quick_one_pass(SqList &L , int low, int high) { int i=low, j=high ;L.r[0]=L.r[i] ; // R[0]作為臨時單元和哨兵do { while ((L.r[i].key<L.r[j].key)&&(j>i))j-- ;if (j>i) { L.r[i]=L.r[j] ;i++; }while ((L.r[i].key<L.r[i].key)&&(j>i))i++ ;if (j>i){ L.r[j]=L.r[i] ; j--; }} while(i!=j) ; /* i=j時退出掃描 */L.r[i]=L.r[0] ; return(i) ; }void quick_Sort(SqList &L , int low, int high) {int k , stack[MAX_STACK] , top=0; do{ while (low<high){k=quick_one_pass(L,low,high); stack[++top]=high ;stack[++top]=k+1 ; /* 第二個子序列的上,下界分別入棧 */high=k-1 ; }if (top!=0) { low=stack[top--] ; high=stack[top--] ;}}while (top!=0&&low<high) ; }int main() {SqList L;InitList_Sq(L);printf("直接插入排序法");straight_insert_sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("選擇排序");simple_selection_sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("冒泡排序");Bubble_Sort(L);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");printf("快速排序");quick_Sort(L,1,L.length);printf("排序成功");for(int i=1;i<L.length;i++)printf("%d ",L.r[i].key);printf("\n");return 0; }

參考文章

https://www.cnblogs.com/leo-lv/p/10639099.html

https://blog.csdn.net/qq_20011607/article/details/82357239

總結

以上是生活随笔為你收集整理的C++——《数据结构与算法》实验——排序算法的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。