首页 > 代码库 > 排序算法 （-）

排序算法 （-）

2024-07-07 08:52:16   228人阅读

以下算法都编译通过，具体原理相信大家都懂，直接上代码。

插入排序

1.直接插入排序

typedef int eleType;
typedef struct{
   eleType key[MAXSIZE],
       int length;
}listSeq;

 void InsertSort(listSeq  &L)
 {
   int j;
   for (int i=1;i<=L.length;i++)
   {
       L.key[0]=L.key[i];
       j=i-1;
      while((L.key[0]<L.key[j])&&j>0)
      {
          L.key[j+1]=L.key[j];
          j--;
      }
       L.key[j+1]=L.key[0];
   }
 }

2.希尔排序算法

void shellInsert(listSeq &L,int d)
{
  int temp,j;
  for (int i=d;i<L.length;i++)    //理解这句话
  {
     temp=L.key[i];
     j=i-d;
     while (temp<L.key[j]&&j>=0)
     {
         L.key[j+d]=L.key[j];
         j-=d;
     }
     L.key[j+d]=temp;
  }
}

void shellSort(listSeq &L)
{
    int d;
    d=L.length/2;
    while (d>1)
    {
        shellInsert(L,d);  //这个地方不需用引用
        d=d/2;
    }
    
}

交换排序

1.冒泡排序

  每一轮选一个最大的元素。

void bubbleSort(listSeq &L)
{
    int temp;
    int flag=1;
    for (int i=0;i<(L.length-1)&&flag;i++)  //当不改变的时候就终止!
    {
        flag=0;
        for (int j=0;j<L.length-i-1;j++)
        {
            if (L.key[j+1]<L.key[j])
            {
                temp=L.key[j];
                L.key[j]=L.key[j+1];
                L.key[j+1]=temp;
                flag=1;
            }
        }
    }

}

2.快排 --冒泡排序的改进

采用递归的方式

int partQuickSort(listSeq &L,int left,int right)
{
   int temp;
   int low=left,high=right;
   temp=L.key[low];
   while (low<high)
   {
       while((L.key[high]>=temp)&&low<high)
           high--;
           L.key[low]=L.key[high];  //此时high被悬空
       
       while((L.key[low]<temp)&&low<high)
           low++;

           L.key[high]=L.key[low];  //此时low被悬空

   }
   L.key[low]=temp;         //这个不要忘记了；
   return low;
}
void QuickSort(listSeq &L,int low,int high)
{
   int mid;
   if (low<high)
   {
     mid=partQuickSort(L,low,high);
     QuickSort(L,low,mid-1);
     QuickSort(L,mid+1,high);
   }
}

归并排序

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
    
    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    
    while (i <= m)
        temp[k++] = a[i++];
    
    while (j <= n)
        temp[k++] = a[j++];
    
    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
    if (first < last)
    {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);    //左边有序
        mergesort(a, mid + 1, last, temp); //右边有序
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }
}

void MergeSort(int a[], int n)  
{
    int *p = new int[n];    //temp
    mergesort(a, 0, n - 1, p);
    delete[] p;
}

int main(int argc, char* argv[])
{
    int a[10];
    int t;
    cout<<"请输入长度:"<<endl;
    cin>>t;
    cout<<"请输入数组:"<<endl;
    for (int i=0;i<t;i++)
    cin>>a[i];
    MergeSort(a,t);
    for (int j=0;j<t;j++)
    cout<<a[j]<<" ";
    cout<<endl;
    return 0;
}


联系
我们