O(n^2)排序 ：选择、插入、冒泡

#include <iostream>
using namespace std;

void printArray(int *arr, int size)
{
    for(int i=0; i<size; ++i)
    {
        cout<< arr[i]<< ' ';
    }
    cout<<endl;
}

void selectionSort(int *arr, int size)
{

    for(int i=0; i<size; i++)
    {
        // 假设当前i为最小值，minIndex为其值索引
        int minIndex = i;
        for (int j=i+1; j<size; j++)
        {
            // 擂台法和i+1之后比较，取出最小的值
            if (arr[minIndex] > arr[j])
                minIndex = j;
        }
        // 交换本次最小的值，放到i位置。
        // if语句为优化
        if (i != minIndex)
            swap(arr[i], arr[minIndex]);
    }
}

void insertionSort(int *arr, int size)
{
	// 插入排序的第一个循环从下标1开始
    for(int i=1; i<size; i++)
    {
        // 保存i位置的元素，i指向无序表
        int tmp = arr[i];
        // 代表i之前的有序表
        int j = i-1;

        // 依次遍历无序表
        for (; j>=0; j--)
        {

            if (arr[j] > tmp)
            {
                arr[j+1] = arr[j];
            }else
            {
                break;
            }
        }

        arr[j+1] = tmp;

    }
}

void bubbleSort(int *arr, int size)
{
    bool hasSorted = true;

    for(int i=0; hasSorted; i++)
    {
        hasSorted = false;
        // 依次遍历无序表
        for (int j=size-1; j>i; j--)
        {
            if (arr[j] < arr[j-1])
            {
                swap(arr[j], arr[j-1]);
                hasSorted = true;
            }

        }

        printArray(arr, size);
    }
}

int main()
{
    int array[6] = {0, -22, 211, 120, 23, 120};
    int size = sizeof (array) / sizeof (*array);

    printArray(array, size);

    // sort algo
    // selectionSort(array, size);
    // insertionSort(array, size);
    // bubbleSort(array, size);

    printArray(array, size);
    return 0;
}

备份地址: 【O(n^2)排序 ：选择、插入、冒泡】