学步园

a. 排序算法
b. 归并排序
c. 快速排序
d. 堆排序
e. 选择排序
f. 希尔排序

Sortable_list.h

#include"Key.h"
#include"List.h"
#include"Timer.h"
#include"Random.h"
typedef Key Record;

template <class Record>
 class Sortable_list:public List<Record>
{
 public:
    Sortable_list();
    Sortable_list(Sortable_list<Record> &s);
    void insertion_sort();
    void selection_sort();
    void shell_sort();
    void merge_sort();
    void quick_sort();
    void heap_sort();
 private:
    int max_key(int low, int high);
    void swap(int low, int high);
    void sort_interval(int start, int increment);
    void merge(int low, int high);
    void recursive_merge_sort(int low, int high);
    void recursive_quick_sort(int low, int high);
    int partition(int low, int high);
    void insert_heap(const Record &current, int low, int high);
    void build_heap();
};

template <class Record> 
Sortable_list<Record>::Sortable_list()
{
    count = 0;
}

template <class Record>
Sortable_list<Record>::Sortable_list(Sortable_list<Record> &s)
{
    count = s.count;
    for (int i = 0; i < count; i++)
        entry[i] = s.entry[i];
}

template <class Record>         
void Sortable_list<Record>::insertion_sort()
{
    int first_unsorted;
    int position;
    Record current;
    
    for (first_unsorted = 1; first_unsorted < count; first_unsorted++) // < count 因为max entry[count-1]
    {
        if (entry[first_unsorted] < entry[first_unsorted-1])   //if true 互换
        {
            position = first_unsorted;
            current = entry[first_unsorted];
            do 
            {
                entry[position] = entry[position-1];   
                position--;
            } while(position > 0 && entry[position-1] > current);
            entry[position] = current;
        }
    }
}

template <class Record>
void Sortable_list<Record>::selection_sort()
{
    for (int position = count - 1; position > 0; position--)
    {
        int max = max_key(0, position);   //先找出最大的，然后放在后面
        swap(max, position);
    }
}

template <class Record>
int Sortable_list<Record>::max_key(int low, int high)
{
    int largest, current;
    largest = low;
    for (current = low + 1; current <= high; current++)
    {
        if (entry[largest] < entry[current])
            largest = current;             //下标操作
    }
    return largest;
}

template <class Record>
void Sortable_list<Record>::swap(int low, int high)
{
    Record temp; 
    temp = entry[low];
    entry[low] = entry[high];
    entry[high] = temp;
}

template <class Record>
void Sortable_list<Record>::shell_sort()
{
    int increment,   // spacing of entries in sublist
        start;       // starting point of sublist
    increment = count;
    do
    {
        increment = increment / 3 + 1;
        for (start = 0; start < increment; start++)
            sort_interval(start, increment);     //modified insertion sort
    } while (increment > 1);
}

template <class Record>
void Sortable_list<Record>::sort_interval(int start, int increment)
{
    int first_unsorted = 0;   // position of first unsorted entry
    int place = 0;            // searches sorted part of list
    Record current;           // used to swap entries
    for (first_unsorted = start +increment; first_unsorted < count; first_unsorted += increment)
    {
        if (entry[first_unsorted] < entry[first_unsorted - increment])
        {
            place = first_unsorted;
            current = entry[first_unsorted];
            // Pull entry[first_unsorted] out of the list
            do
            {
                // Shift all previous entries one place down the list
                entry[place] = entry[place - increment];
                // until the proper place is found
                place -= increment;
                // Position place is now availabe for insertion
            } while (place > start && entry[place - increment] > current);
            entry[place] = current;
        }
    }
}

template <class Record>
void Sortable_list<Record>::merge_sort()
{
    recursive_merge_sort(0, count-1);
}

template <class Record>
void Sortable_list<Record>::recursive_merge_sort(int low, int high)
{
    if (high > low)
    {
        recursive_merge_sort(low, (high + low) / 2);
        recursive_merge_sort( (high + low) / 2 + 1, high);
        merge(low, high);
    }
}

template <class Record> 
void Sortable_list<Record>::merge(int low, int high)
{
    Record* temp = new Record[high - low + 1];
    int index = 0;
    int index1 = low, mid = (low + high) / 2, index2 = mid + 1;
    while (index1 <= mid && index2 <= high)
    {
        if (entry[index] < entry[index2])
            temp[index++] = entry[index1++];
        else
            temp[index++] = entry[index2++];
    }
    while (index1 <= mid)
        temp[index++] = entry[index1++];
    while (index2 <= high)
        temp[index++] = entry[index2++];
    for (index = low; index <= high; index++)
        entry[index] = temp[index - low];
    delete []temp;    
}

template <class Record>
void Sortable_list<Record>::quick_sort()
{
    recursive_quick_sort(0, count - 1);
}

template <class Record>
void Sortable_list<Record>::recursive_quick_sort(int low, int high)
{
    int pivot_position;
    if (low < high)
    {
        pivot_position = partition(low, high);
        recursive_quick_sort(low, pivot_position - 1);
        recursive_quick_sort(pivot_position + 1, high);
    }
}

template <class Record>
int Sortable_list<Record>::partition(int low, int high)
{
    Record pivot;
    int i,                // used to scan through the list 
        last_small;        // position of th last key less than pivot
    swap(low, (low + high) / 2);
    pivot = entry[low]; // First entry is now pivot
    last_small = low;

    for (i = low + 1; i < high; i++)
    /* At the beginning of each iteration of this loop, we have the following condition:
              If low < j <= last_small  then entry[j].key < pivot.
              If last_small < j < i   then entry[j].key >= pivot */
    {
        if (entry[i] < pivot)
        {
            last_small = last_small + 1;
            swap(last_small, i);     // Move large entry to right and small to left
        }
    }

    swap(low, last_small);           // Put the pivot into its proper position
    return last_small;
}

template <class Record>
void Sortable_list<Record>::heap_sort()
{
    Record current;
    int last_unsorted;
    build_heap();
    for (last_unsorted = count + 1; last_unsorted > 0; last_unsorted--)
    {
        current = entry[last_unsorted];
        entry[last_unsorted] = entry[0];
        insert_heap(current, 0, last_unsorted - 1);
    }
}

template <class Record>
void Sortable_list<Record>::build_heap()
{
    int low;
    for (low = count / 2 - 1; low >= 0; low--)
    {
        Record current = entry[low];
        insert_heap(current, low, count - 1);
    }
}
template <class Record>
void Sortable_list<Record>::insert_heap(const Record &current, int low, int high)
{
    int large; 
    large = 2 * low + 1;
    while (large <= high)
    {
        if (large < high && entry[large] < entry[large+1])
            large++;
        if (current >= entry[large])
            break;
        else
        {
            entry[low] = entry[large];
            low = large;
            large = 2 * low + 1;
        }
    }
    entry[low] = current;
}

main.cpp
注意对fstream的使用
 fstream f("a.txt");  =  fstream f;  f.open("a.txt");
操作完必须 f.close();
该文件中 两个do{} while(); 用的比较好，第二个指令[q]uit时，可自动跳到上一层

#include"Sortable_list.h"
#include<fstream>

void show(char *comment, double t, int comparisions)
{
    cout












														
							

返回

【上篇】励志故事：想优秀就要拼命
【下篇】加快开关机速度

作者: bvfgrrr

• 该日志由 bvfgrrr 于12年前发表在综合分类下，最后更新于 2012年02月11日.
• 转载请注明: 排序算法 | 学步园 +复制链接

抱歉!评论已关闭.