7 sorting methods are as follows:
Directly insert into sorting insertsort ()
Hill sort shellsort ()
Bubble sorting bubblesort ()
fast sort Quicksort ()
Simple selection of Selectsort ()
Heap sort heapsort ()
Mergly sorting Mergesort ()
[If you need to find it yourself, you will not explain one by one here]
Comprehensive case
sort.h
#ifndef SORT_H
#define SORT_H
#include<iostream>
#include<cmath>
using namespace std;
class Sort
{
public:
Sort(int r[ ], int n);
~Sort( );
void InsertSort( ); // Put directly into sorting
void ShellSort( ); // Hill Sort
void BubbleSort( ); // Bubble Sorting
void QuickSort(int first, int last); // Quick Sorting
void SelectSort( ); // Select Sorting
void HeapSort( ); // Heap sorting
void MergeSort1(int first, int last);// Consultation Sorting
void MergeSort2( ); // Comebacks are not recursive sorting
void Print( ); // Cycles traverse output
private:
int Partition(int first, int last); // The division algorithm of fast sorting
void Sift(int k, int last); //
void Merge(int first1, int last1, int last2); //
void MergePass(int h); //
int *data; // Sorting array
int length; // array length
};
// Construction function
Sort :: Sort(int r[ ], int n){
data = new int[n];
for (int i = 0; i < n; i++)
data[i] = r[i];
length = n;
}
// Discirate function
Sort :: ~Sort( ){
delete[ ] data;
}
// Traversing output
void Sort :: Print( ){
cout<<"The array after sorting is:"<<endl;
for (int i = 0; i < length; i++){
cout << data[i] << "\t";
}
cout << endl;
}
// Put directly into sorting
void Sort :: InsertSort( ){
int i, j, temp;
for (i = 1; i < length; i++){
temp = data[i]; // Temporary storage to be inserted
j = i - 1; // Compare the array elements before I, i <j, then move one bit back, j move one forward, otherwise I will be stored in
while (j >= 0 && temp < data[j]){
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
// Hill Sorting
void Sort :: ShellSort( ){
int d, i, j, temp;
for (d = length/2; d >= 1; d = d/2) // Increase to D for direct inserting and sorting
{
for (i = d; i < length; i++){
// Make a trip to Hill
temp = data[i]; // Temporary storage to be inserted recorded
for (j = i - d; j >= 0 && temp < data[j]; j = j - d)
data[j + d] = data[j]; // Record the back of D position
data[j + d] = temp;
}
}
}
// Bubble Sorting
void Sort :: BubbleSort( ){
int j, exchange, bound, temp;
exchange = length - 1; // The first time the bubble sorting range is [0 ~ length-1]
while (exchange != 0){
bound = exchange; exchange = 0;
for (j = 0; j < bound; j++) // The range of a bubble sorting is [0 ~ Bound]
if (data[j] > data[j+1]) {
temp = data[j]; data[j] = data[j+1]; data[j+1] = temp;
exchange = j; // Record the location of each record exchange
}
}
}
// The division algorithm of fast sorting
int Sort :: Partition(int first, int last)
{
int i = first, j = last, temp;
while (i < j){
while (i < j && data[i] <= data[j]) j--; /*Scan on the right* /
if (i < j) {
temp = data[i]; data[i] = data[j]; data[j] = temp;
i++;
}
while (i < j && data[i] <= data[j]) i++; /*A scan from the left side* /
if (i < j) {
temp = data[i]; data[i] = data[j]; data[j] = temp;
j--;
}
}
return i; /*i is the final position of the axis value record* /
}
// Quick Sorting
void Sort :: QuickSort(int first, int last){
if (first == last) return; /*The length of the interval is 1, and the recursive end will end* /
else {
int pivot = Partition(first, last);
QuickSort(first, pivot-1);
QuickSort(pivot+1, last);
}
}
// Select Sorting
void Sort :: SelectSort( ){
int i, j, index, temp;
for (i = 0; i < length-1; i++){
index = i;
for (j = i + 1; j < length; j++)
if (data[j] < data[index]) index = j;
if (index != i) {
temp = data[i]; data[i] = data[index]; data[index] = temp;
}
}
}
// The pile of stacking method
void Sort :: Sift(int k, int last){
int i, j, temp;
i = k; j =2 * i + 1; // i is the adjustment node, J is the left child of I
while (j <= last) // No leaf has been performed yet
{
if (j < last && data[j] < data[j+1]) j++;// j refers to the larger one to the left and right children
if (data[i] > data[j]) break; // already pile
else {
temp = data[i]; data[i] = data[j]; data[j] = temp;
i = j; j = 2 * i + 1; // The adjustment node is located at the position of the node j
}
}
}
// Heap sorting
void Sort :: HeapSort( ){
int i, temp;
for (i = ceil(length/2) - 1; i >= 0; i--) // From the last branch node to the root node
Sift(i, length-1) ;
for (i = 1; i < length; i++)
{
temp = data[0]; data[0] = data[length-i]; data[length-i] = temp;
Sift(0, length-i-1); // Rebuilding heap
}
}
// recursive combination algorithm in sorting
void Sort :: Merge(int first1, int last1, int last2)
{
int *temp = new int[length];
int i = first1, j = last1 + 1, k = first1;
while (i <= last1 && j <= last2){
if (data[i] <= data[j]) temp[k++] = data[i++];
else temp[k++] = data[j++];
}
while (i <= last1)
temp[k++] = data[i++];
while (j <= last2)
temp[k++] = data[j++];
for (i = first1; i <= last2; i++)
data[i] = temp[i];
delete[ ] temp;
}
// recursive algorithm of mergers and sorting
void Sort :: MergeSort1(int first, int last)
{
if (first == last) return;
else {
int mid = (first + last)/2;
MergeSort1(first, mid);
MergeSort1(mid+1, last);
Merge(first, mid, last);
}
}
// Non -recucted merger sorting algorithm
void Sort :: MergePass(int h){
int i = 0;
while (i + 2 * h <= length){
// There are two sub -sequences with H with a length
Merge(i, i+h-1, i+2*h-1);
i = i + 2 * h;
}
if (i + h < length) // The length of the two sub -sequences is less than H
Merge(i, i+h-1, length-1);
}
// Non -recucted mergers and sorting
void Sort :: MergeSort2( ){
int h = 1; // The length of the child sequence is 1
while (h < length){
MergePass(h); // A merger and sorting
h = 2 * h;
}
}
#endif
sort.cpp
#include "sort.h"
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int len,select=-1;
int r[10]={
12,43,27,54,23,75,10,42,52,21};
// core << "Please enter the array length to be sorted:";
// cin>>len;
// int *r = new int[len];
// core << "Please enter the array to be sorted:";
// for(int i=0; i<len; i++){
// cin>>r[i];
// }
// cout<<endl;
len=10;
Sort L(r,len);
cout<<"1. Directly insert sort \ t 2. Hill Sort"<<endl;
cout<<"3. Bubble sorting \ t 4. Quick Sort"<<endl;
cout<<"5. Simple selection of sort \ t 6. Heap sorting"<<endl;
cout<<"7. Consultation sorting \ t 8. Macro -recursively sorting"<<endl;
cout<<"Please enter the sorting method number to be used:"<<endl;
cin>>select;
switch(select){
// case 0:system.exit(0);break;
case 1:L.InsertSort();break;
case 2:L.ShellSort();break;
case 3:L.BubbleSort();break;
case 4:L.QuickSort(0,len-1);break;
case 5:L.SelectSort();break;
case 6:L.HeapSort();break;
case 7:L.MergeSort1(0,len-1);break;
case 8:L.MergeSort2();break;
default:cout<<endl;cout<<"Input sorting number is wrong!"<<endl;
}
cout<<endl;
L.Print();
// delete[] r;
return 0;
}
From “Data Structure -From Concept to C ++ Realization (3rd Edition)” example example