排序算法的实现（冒泡，选择，插入 O（N*N）–理解方法实现

程序员淑鹏技术 2022年11月21日

0 收藏 449 点赞 3,410 浏览 1303 个字

以前也看过很多排序算法的原理，每次都想自己实现一下，一直都再拖，现在着牛课网学习算法课程，希望自己能够坚持练习。

//对于一个int数组，请编写一个选择冒泡算法，对数组元素排序。
//给定一个int数组A及数组的大小n，请返回排序后的数组。
//测试样例：
//[1, 2, 3, 5, 2, 3], 6
//[1, 2, 2, 3, 3, 5]#include <iostream>
using namespace std;
#include<string>void printResult(string str,int* A,int n)
{
    cout << str << "的结果:\n";
    for (int i = ; i < n; i++)
    {
        cout << A[i] <<" ";
    }
    cout << endl;
}void swap(int a, int b)
{
    int temp=a;
    a = b;
    b = a;
}class BubbleSort {
public:
    int* bubbleSort(int* A, int n) {
        // write code here
        for (int i = ; i<n; i++)
        {
            for (int j = ; j<n - i - ; j++)
            {
                if (A[j]>A[j + ])
                {
                    int temp = A[j];
                    A[j] = A[j + ];
                    A[j + ] = temp;
                }
            }
        }
        return A;
    }
};//请编写一个选择排序算法
class SelectionSort {
public:
    int* selectionSort(int* A, int n) {
        // write code here
        int k = ;
        for (int i = ; i < n-; i++)
        {
            k = i;
            for (int j = i; j < n; j++)
            {
                if (A[k]>A[j])
                {
                    k = j;
                }
            }
            if (k!=i)
            {
                int temp = A[i];
                A[i] = A[k];
                A[k] = temp;
            }
        }
        return A;
    }
};//请编写一个选择插入算法class InsertionSort
{
public:
    int* insertionSort(int* A, int n)
    {
        for (int i = ; i < n; i++)
        {
            int temp = A[i];
            int j = i - ;
            for (; j >= ;j--)   //j前面的已经排好序，从后面往前比较，当没有比当前值大的时候bereak;
            {
                if (A[j]>temp)
                {
                    A[j + ] = A[j];
                }
                else
                {
                    break;
                }
            }
            A[j + ] = temp;
        }
        return A;
    }
};int main()
{    int N = ;
    cout << "排序数据个数：\n";
    cin >> N;
    int* A = new int[N];
    cout << "请输入待排序的数据：\n";
    for (int i = ; i < N; i++)
    {
        cin >> A[i];
    }    BubbleSort bubble;
    bubble.bubbleSort(A,N);
    printResult("bubbleSort", A, N);    SelectionSort select;
    select.selectionSort(A, N);
    printResult("selectSort", A, N);    InsertionSort insert;
    insert.insertionSort(A, N);
    printResult("InsetSort", A, N);    return ;
}