排序 - c++代码库

[c++]代码库
void print(int a[], int n ,int i){  
    cout<<i <<":  ";  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<" ";  
    }  
    cout<<endl;  
}  
void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}
//直接插入排序
void StraightInsertSort(int a[], int num)
{
    cout<<"StraightInsertSort "<<endl;  
 
    for (int i=1; i<num; i++)
    {
        if (a[i] < a[i-1])   //插入元素小于前一个元素，向前插入
        {
            int x = a[i];
            int k = i-1;
            a[i] = a[i-1];
            while (x < a[k]) //依次向后移动
            {
                a[k+1] = a[k];
                k--;
            }
            a[k+1] = x;
        }
        print(a, num, i);
    }
}
//希尔排序，改进直接插入排序
void ShellInsertSort(int a[], int num, int dk)
{
    cout<<"dk= "<<dk<<endl;  
 
    for (int i=dk; i<num; i++)
    {
        if (a[i] < a[i-dk])
        {
            int x = a[i];
            int k = i - dk;
            a[i] = a[k];
            while (x < a[k])
            {
                a[k+dk] = a[k];
                k -= dk;
            }
            a[k+dk] = x;
        }
        print(a, num, i);
    }
}
void ShellSort(int a[], int num)
{
    cout<<"ShellInsertSort "<<endl;  
 
    int dk = num/2;
    while (dk >= 1)
    {
        ShellInsertSort(a, num, dk);
        dk /= 2;
    }
}
 
//简单选择排序
void SimpleSelectSort(int a[], int num)
{
    for (int i=0; i<num; i++)
    {
        int minNum = a[i];
        int pos = -1;
        for (int k=i+1; k<num; k++)
        {
            if (minNum > a[k])
            {
                minNum = a[k];
                pos = k;
            }
        }
        if (pos != -1)
        {
            a[pos] = a[i];
            a[i] = minNum;
        }
        print(a, num, i);
    }
}
//双向选择排序
void SelectionExSort(int a[], int num)
{
    for (int i=1; i<=num/2; i++)
    {
        int maxPos = i-1;
        int minPos = num-i;
        for (int k=i+1; k<num-i; k++)
        {
            if (a[maxPos] < a[k])
            {
                maxPos = k;
            }
            if (a[minPos] > a[k])
            {
                minPos = k;
            }
        }
        if (a[minPos] < a[i-1])
        {
            swap(a[minPos], a[i-1]);
        }
 
        if (a[maxPos] > a[num-i])
        {
            swap(a[maxPos], a[num-i]);
        }
 
        print(a, num, i);
    }
}
 
//冒泡排序
void BubbleSort(int a[], int num)
{
    for (int i=0; i<num; i++)
    {
        for (int k=0; k<num-1-i; k++)
        {
            if (a[k] > a[k+1])
            {
                swap(a[k], a[k+1]);
            }
        }
        print(a, 10, i);
    }
}
//简化冒泡排序，如果之后有序，不在排列
void BubbleSort_1(int a[], int num)
{
    int endPos = num-1;
    int i = 0;
    while (endPos > 0)
    {
        int pos = 0;
        for (int k=0; k<endPos; k++)
        {
            if (a[k] > a[k+1])
            {
                pos = k;
                swap(a[k], a[k+1]);
            }
        }
        endPos = pos;
        print(a, 10, i++);
    }
}
//双向冒泡排序
void BubbleSort_2(int a[], int num)
{
    int lowPos = 0;
    int highPos = num-1;
    int k;
    int i = 0;
    while (lowPos < highPos)
    {
        for (k=lowPos; k<highPos; k++)
        {
            if (a[k] > a[k+1])
            {
                swap(a[k], a[k+1]);
            }
        }
        highPos--;
        print(a, 10, i);
        for (k=highPos; k>lowPos; k--)
        {
            if (a[k] < a[k-1])
            {
                swap(a[k], a[k-1]);
            }
        }
        lowPos++;
        print(a, 10, i++);
    }
}
 
static int i = 0;
//快速排序
void QuickSort(int a[], int low, int high)
{
    if (low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[low];
    while (first < last)
    {
        while (first < last && a[last] >= key)
        {
            last--;
        }
        a[first] = a[last];
        while (first < last && a[first] <= key)
        {
            first++;
        }
        a[last] = a[first];
    }
    a[first] = key;
    print(a, 10, i++);
    QuickSort(a, low, first-1);
    QuickSort(a, first+1, high);
}
 
//归并排序
void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex)
{
    int i = startIndex,j=midIndex+1,k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1)
    {
        if(sourceArr[i]<sourceArr[j])
            tempArr[k++] = sourceArr[i++];
        else
            tempArr[k++] = sourceArr[j++];
    }
    while(i!=midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j!=endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex;i<=endIndex;i++)
        sourceArr[i] = tempArr[i];
}
//内部使用递归
void MergeSort(int sourceArr[],int tempArr[],int startIndex,int endIndex)
{
    int midIndex;
    if(startIndex<endIndex)
    {
        midIndex=(startIndex+endIndex)/2;
        MergeSort(sourceArr,tempArr,startIndex,midIndex);
        MergeSort(sourceArr,tempArr,midIndex+1,endIndex);
        Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);
    }
    print(sourceArr, 10, i++);
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

排序

[c++]代码库

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
