常考的排序算法

冒泡排序

#include<iostream>
#include<string>
using namespace std;
//void Shellsort(int A[], int n)
//{
//    int d, i, j;
//    for (d = n / 2; d >= 1; d = d / 2)
//    {
//        for (i = d + 1; i <= n; i++)
//        {
//            if (A[i] <=A[i - d])
//            {
//                A[0] = A[i];
//                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
//                    A[j + d] = A[j];
//                A[j + d] = A[0];
//            }
//
//        }
//    }
//}
void bullsort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = 0; j <n-i - 1; j++)
        {
            if(A[j]>A[j+1])
            {
                int temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
                flag = true;
            }
        }
        if (flag == false)
            return;
    }
}
int main()
{
    int a[100];
    for (int i =0; i < 10; i++)
    {
        cin >> a[i];
    }
    //Shellsort(a, 10);
    /*for (int i = 1; i < 10; i++)
    {
        cout << a[i] << " ";
    }*/
    bullsort(a, 10);
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << " ";
    }
}

选择排序

#include<iostream>
#include<string>
using namespace std;
void selectsort(int A[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < n; j++)
        {
            if (A[j] < A[min]) min = j;
        }
        if (min != i)
        {
            int temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
    }
}
int main()
{
    int a[100];
    for (int i =0; i < 10; i++)
    {
        cin >> a[i];
    }
    selectsort(a, 10);
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << " ";
    }
}

快速排序

#include<iostream>
#include<string>
using namespace std;
int partition(int A[], int low, int high)
{
    int pivot = A[low];
    while (low < high)
    {
        while (low < high && A[high] >= pivot)--high;
        A[low] = A[high];
        while (low < high && A[low] <= pivot)++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}
void quicksort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = partition(A, low, high);
        quicksort(A, low, pivotpos - 1);
        quicksort(A, pivotpos + 1, high);
    }
}
int main()
{
    int a[100];
    for (int i =0; i < 10; i++)
    {
        cin >> a[i];
    }
    quicksort(a, 0,9);
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << " ";
    }
}

堆排序

#include<iostream>
#include<string>
using namespace std;
void Headadjust(int A[], int k, int len)//将以k为根的子树调整为大根堆
{
    A[0] = A[k];//A[0]暂存子树的根节点
    for (int i = 2 * k; i <= len; i *= 2)//沿key较大的子节点向下筛选
    {
        if (i < len && A[i] < A[i + 1])i++;//取key较大的子节点的下标
        if (A[0] >= A[i]) break;//筛选结束
        else {
            A[k] = A[i];//将A[i]调整到双亲结点上
            k = i;//修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];
}
void Buildmaxheap(int A[], int len)//建立大根堆
{
    for (int i = len / 2; i > 0; i--)
    {
        Headadjust(A, i, len);
    }
}
void Heapsort(int A[], int len)
{
    Buildmaxheap(A, len);//初始建堆
    for (int i = len; i > 1; i--)
    {
        int temp = A[i];//堆顶元素和堆底元素交换
        A[i] = A[1];
        A[1] = temp;
        Headadjust(A, 1, i - 1);//把剩余的待排序元素整理成堆
    }
}
int main()
{
    int a[100] = { 0 };
    for (int i = 1; i <= 10; i++)
    {
        cin >> a[i];
    }
    Heapsort(a, 10);
    for (int i = 1; i <= 10; i++)
    {
        cout<<a[i]<<" ";
    }
}

归并排序

#include<iostream>
#include<string>
using namespace std;
int B[100] = { 0 };//辅助队列
//各自有序，将两个部分归并
void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    for (k = low; k <= high; k++)
    {
        B[k] = A[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        if (B[i] <=B[j])
        {
            A[k] = B[i++];//将较小值复制到A中
        }
        else {
            A[k] = B[j++];
        }
    }
    while (i <= mid) A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}
void Mergesort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;//从中间划分
        Mergesort(A, low, mid);//对左半部分归并排序
        Mergesort(A, mid + 1, high);//对右半部分归并排序
        Merge(A, low, mid, high);//归并
    }
}
int main()
{
    int a[100] = { 0 };
    for (int i = 0; i < 10; i++)
    {
        cin >> a[i];
    }
    Mergesort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        cout << a[i] << " ";
    }

}

希尔排序

#include<iostream>
#include<string>
using namespace std;
void Shellsort(int A[], int n)
{
    int d, i, j;
    for (d = n / 2; d >= 1; d = d / 2)
    {
        for (i = d + 1; i <= n; i++)
        {
            if (A[i] <=A[i - d])
            {
                A[0] = A[i];
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                    A[j + d] = A[j];
                A[j + d] = A[0];
            }

        }
    }
}

int main()
{
    int a[100];
    for (int i =1; i <= 10; i++)
    {
        cin >> a[i];
    }
    Shellsort(a, 10);
    for (int i = 1; i <= 10; i++)
    {
        cout << a[i] << " ";
    }
}