main.cpp

排序算法,初学数据结构及算法的入门者值得一看

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "main.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)
{
    int values[30], i;
    for (i = 0; i < 30; i++)
    values[i] = rand() %100;
    long t = GetTickCount();
    bubble_sort(values, 30);
    for (i = 0; i < 30; i++)
        printf("%d ", values[i]);

    printf("\nsort complete. Duration: %ld\n", GetTickCount()-t);
}
//---------------------------------------------------------------------------

// 冒泡排序
void __fastcall TForm1::bubble_sort(int array[], int size)
{
    int temp, i , j;
    for (i = 0; i < size; i++)
        for(j = 0; j < size; j++)
            if (array[i] < array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
}

void __fastcall TForm1::Button2Click(TObject *Sender)
{
    int values[30], i;
    for (i = 0; i < 30; i++)
    values[i] = rand() %100;
    long t = GetTickCount();
    selection_sort(values, 30);
    for (i = 0; i < 30; i++)
        printf("%d ", values[i]);

    printf("\nsort complete. Duration: %ld\n", GetTickCount()-t);
}
//---------------------------------------------------------------------------

//选择排序
void __fastcall TForm1::selection_sort(int array[], int size)
{
    //TODO: Add your source code here
    int temp, current, j;

    for (current = 0; current < size; current++)
      for (j = current+1; j < size; j++)
        if (array[current] > array[j])
        {
          temp = array[current];
          array[current] = array[j];
          array[j] = temp;
        }
}

void __fastcall TForm1::Button3Click(TObject *Sender)
{
    int values[50], i;
    for (i = 0; i < 50; i++)
    values[i] = rand() %100;
    long t = GetTickCount();
    shell_sort(values, 50);
    for (i = 0; i < 50; i++)
        printf("%d ", values[i]);

    printf("\nsort complete. Duration: %ld\n", GetTickCount()-t);
}
//---------------------------------------------------------------------------

// 希尔排序
void __fastcall TForm1::shell_sort(int array[], int size)
{
    //TODO: Add your source code here
    int temp, gap, i, exchange_occurred;

    gap = size / 2;
    do
    {
        do
        {
            exchange_occurred = 0;
            for (i = 0; i < size - gap; i++)
              if (array[i] > array[i+gap])
              {
                temp = array[i];
                array[i]=array[i+gap];
                array[i+gap]=temp;
                exchange_occurred = 1;
              }
        }
        while(exchange_occurred);
    }
    while(gap=gap/2);
}

void __fastcall TForm1::Button4Click(TObject *Sender)
{
    int values[100], i;
    for (i = 0; i < 100; i++)
    values[i] = rand() %100;
    long t = GetTickCount();
    quick_sort(values, 0, 99);
    for (i = 0; i < 100; i++)
        printf("%d ", values[i]);

    printf("\nsort complete. Duration: %ld\n", GetTickCount()-t);
}
//---------------------------------------------------------------------------

void __fastcall TForm1::quick_sort(int array[], int first, int last)
{
    //TODO: Add your source code here
    int temp, low, high, list_separator;

    low = first;
    high = last;
    list_separator = array[(first+last)/2];
    do
    {
      while(array[low] < list_separator)
        low++;
      while (array[high] < list_separator)
        high--;
      if (low <= high)
      {
        temp = array[low];
        array[low++] = array[high];
        array[high--] = temp;
      }
    }
    while (low <= high);
    if (first < high)
      quick_sort(array, first, high);
    if (low < last)
      quick_sort(array, low, last);
}