常用排序算法-蒲公英云

常用排序算法

蔚落 2022-04-16 04:49 286阅读 0赞

插入排序：

#include "main.h"
void insertSort(int *data, int length)
{
    int pos, i , temp;
    for (pos = 1; pos < length; pos++)
    {
        temp = data[pos];
        for (i = pos - 1; i >= 0; i--)
        {
            if (temp < data[i])
            {
                data[i + 1] = data[i];
                if (0 == i)
                {
                    data[0] = temp;
                    break;
                }
            }
            else
            {
                data[i + 1] = temp;
                break;
            }
        }
    }
}

２.　选择排序：

#include "main.h"
void selectSort(int *data, int length)
{
    int max, pos, i;
    for (pos = length - 1; pos > 0; pos--)
    {
        max = 0;
        for (i = 1; i <= pos; i++)
        {
            if (data[max] < data[i])
            {
                max = i;
            }
        }
        if (max != pos)
        {
            swap(data, max, pos);
        }
    }
}

３.　冒泡排序：

#include "main.h"
void popSort(int *data, int length)
{
    int pos, i;
    for (pos = length - 1; pos >= 1; pos--)
    {
        for (i = 0; i < pos; i++)
        {
            if (data[i] > data[i + 1])
            {
                swap (data, i, i + 1);
            }
        }
    }
}

４.　快速排序：

#include "main.h"
/**
  *  Partition of the quickSort
  */
int partition(int *data, int start, int end)
{
    int i = start + 1, j = end;
    if (start >= end)
    {
        return start;
    }
    while (1)
    {
        while (i <= j && data[start] >= data[i])
        {
            i++;
        }
        while (i <= j && data[start] < data[j])
        {
            j--;
        }
        if (i < j)
        {
            swap(data, i, j);
        }
        else
        {
            swap(data, start, j);
            return j;
        }
    }
}
void quickSort(int *data, int start, int end)
{
    int pos;
    if (start >= end)
    {
        return;
    }
    pos = partition(data, start, end);
    quickSort(data, start, pos - 1);
    quickSort(data, pos + 1, end);
}

５.　归并排序：

#include "main.h"
void merge(int *data, int start, int middle, int end)
{
    int i = start, j = middle + 1;
    int pos = 0;
    int *temp = NULL;
    if (start >= end)
    {
        return;
    }
    temp = (int *)malloc((end - start + 1) * sizeof(int));
    while (i <= middle && j <= end)
    {
        temp[pos++] = data[i] <= data[j] ? data[i++] : data[j++];
    }
    while (i <= middle)
    {
        temp[pos++] = data[i++];
    }
    while (j <= end)
    {
        temp[pos++] = data[j++];
    }
    pos = 0;
    while (pos < end - start + 1)
    {
        data[start + pos] = temp[pos++];
    }
    free(temp);
}
void mergeSort(int *data, int length)
{
    int i, step;
    for (step = 1; step < length; step *= 2)
    {
        for (i = 0; i + step < length; i += 2 * step)
        {
            (i + 2 * step - 1 < length) ? 
                merge(data, i, i + step - 1, i + 2 * step - 1) : merge(data, i, i + step - 1, length - 1);
        }
    }
}

６.　堆排序：

#include "main.h"
void adjust(int *data, int pos, int length)
{
    int parent = pos, child = 2 * parent + 1;
    while (child < length)
    {
        if (child + 1 < length && data[child + 1] > data[child])
        {
            child++;
        }
        if (data[parent] < data[child])
        {
            swap(data, parent, child);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void createHeap(int *data, int length)
{
    int pos;
    for (pos = (length - 2) / 2; pos >= 0; pos--)
    {
        adjust(data, pos, length);
    }
}
void heapSort(int *data, int length)
{
    int pos;
    createHeap(data, length);
    for (pos = length - 1; pos >= 0; pos--)
    {
        swap(data, pos, 0);
        adjust(data, 0, pos);
    }
}
void heapSortNoWrap(int *data, int length)
{
    int start, end, child, parent, temp;
    end = length - 1;
    start = (end - 1) / 2;
    while (1)
    {
        if (0 <= start)
        {
            temp = data[start--];
        }
        else
        {
            if (0 == end)
            {
                return;
            }
            else
            {
                temp = data[end];
                data[end--] = data[0];
            }
        }
        parent = start + 1;
        child = 2 * parent + 1;
        while (child <= end)
        {
            if (child + 1 <= end && data[child + 1] > data[child])
            {
                child++;
            }
            if (temp < data[child])
            {
                data[parent] = data[child];
                parent = child;
                child = 2 * parent + 1;
            }
            else
            {
                break;
            }
        }
         data[parent] = temp;
    }
}