記序排序

記序排序是交換排序的一種，利用數組元素序號快速定位最大的元素，把最大的元素往後調藉以達到排序作用的排序算法。

基本介紹

• 中文名：記序排序
• 外文名：jixu sort
• 用途：用元素序號進行排序

基本思想

記序排序的算法是：

1. 初始化操作，初始化數組a[1..n]；
   
2. 數組下標變數先從數組a[1..n]首端和尾端向中間移動，比較選出關鍵字較大的2└^log₂ⁿ┘個元素；
   
3. 經過└log₂n┘次循環比較選出數值最大的元素放入a[0]；
   
4. 將最大元素a[0]與隊尾元素a[n-1]交換；
   
5. 以上2-4步驟執行n遍；
   

性質

最壞時間複雜度o(nlogn)

平均時間複雜度o(nlogn)

空間複雜度o(1)

穩定排序

示例

記序排序第一回排序

記序排序第一輪

15 30 25 18 16 49 65 80 31

交換15和31

31 30 25 18 16 49 65 80 15

31 30 25 18 16 49 65 80 15

交換30和80

31 80 25 18 16 49 65 30 15

31 80 25 18 16 49 65 30 15

交換25和65

31 80 65 18 16 49 25 30 15

31 80 65 18 16 49 25 30 15

交換18和49

31 80 65 49 16 18 25 30 15

記序排序第二輪

31 80 65 49 16 18 25 30 15

31 80 65 49 16 18 25 30 15

記序排序第三輪

31 80 65 49 16 18 25 30 15

交換31和65

65 80 31 49 16 18 25 30 15

記序排序第四輪

65 80 31 49 16 18 25 30 15

交換65和80

80 65 31 49 16 18 25 30 15

最後將80調到數組最後

15 65 31 49 16 18 25 30 80

記序排序第二回

15 65 31 49 16 18 25 30 80

以此類推，將數組最大元素放在首位，然後調往最後，再排前面無序的

套用

數組記序排序c語言代碼

#include<stdio.h> #include<stdlib.h>void main() { int i,j,p,t,k,temp,n=100;int a[100];printf("排序前:\n");for(i=0;i<n;i++){ a[i]=rand(); printf("a[%d]=%d\t",i,a[i]); if((i+1)%5==0)     printf("\n");}t=n; while(t)                     {     i=p=t;    k=1;           while(i)     {       i=i/2;       k=2*k;     }     k=k/2;                         while(k)                   {            for(i=0,j=p-1;i<j;i++,j--)         if(a[i]<a[j])         {           temp=a[i];         a[i]=a[j];         a[j]=temp;        } ;          k=k/2;      p=(p+1)/2;     } temp=a[t-1];a[t-1]=a[0];a[0]=temp; t--; } printf("排序後:\n");for(i=0;i<n;i++){ printf("a[%d]=%d\t",i,a[i]); if((i+1)%5==0)     printf("\n");}}

帶頭結點單鍊表記序排序代碼#include <stdio.h>  #include <stdlib.h>  typedef int ElemType;#define N 10   //定義結點類型   typedef struct Node  {      ElemType data;              //單鍊表中的數據域       struct Node *next;          //單鍊表的指針域   }Node,*LinkedList;  LinkedList Creat(int n){    LinkedList head,r,p;    int x,i;    head=(Node*)malloc(sizeof(Node));    r=head;    printf("輸入數字:\n");    for(i=n;i>0;i--)    {    scanf("%d",&x);    p=(Node*)malloc(sizeof(Node));    p->data=x;    r->next=p;    r=p;    }    r->next=NULL;    return head;} int sizeList(LinkedList L){    Node *p=L;    int size = 0;     while(p->next)    {        size++;         //遍歷鍊表size大小比鍊表的實際長度小1        p= p->next;    }       return size;    //鍊表的實際長度} LinkedList LinkedListSortT(LinkedList L){    Node *p,*q;    int i,j,k,t,m,n,l,s;    t=n=sizeList(L);    ElemType temp;    while(t)    {      i=l=t;      k=1;           while(i)     {       i=i/2;       k=2*k;     }     k=k/2;         while(k)       {                          for(i=0,j=l-1;i<j;i++,j--)         {           m=i+1;           s=j+1;           p=q=L;           while(m--) {p=p->next;}           while(s--) {q=q->next;}           if(p->data<q->data)           {             temp=p->data;             p->data=q->data;             q->data=temp;           }         }        k=k/2;        l=(l+1)/2;      }        p=q=L->next;        k=t;        while(--k) {q=q->next;}           temp=p->data;           p->data=q->data;           q->data=temp;        t--;       }  return L; }void output(LinkedList head){    LinkedList p;    p=head->next;    do{        printf("%3d",p->data);p=p->next;    }while(p);    printf("\n");} void main(){    LinkedList L;    int n;    printf("排序多少數字:\n");    scanf("%d",&n);        L=Creat(n);    printf("排序前:\n");       output(L);    LinkedListSortT(L);    printf("排序後:\n");    output(L);}