每次开始动手写算法，都是先把插入排序，冒泡排序写一遍，十次有九次是重复的，所以这次下定决心，将所有常规的排序算法写了一遍，以便日后熟悉。
以下代码总用一个main函数和一个自定义的CommonFunction函数
CommonFunction函数中定义了一个交换函数和一个输出函数：
/*
* CommonFunction.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #pragma once
namespace section4 {
void swap(int *first, int *second) {
int temp;
temp = *first;
*first = *second;
*second = temp;
} void printfByStep(int *a, int i, int len) {
int k;
printf("The result of the %dth step\n", i);
for (k = ; k < len; k++)
printf("%d ", a[k]);
printf("\n");
}
}
main函数：
/*
* SortMain.cpp
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<sys/timeb.h>
#include "BubbleSort.h"
#include "SelectionSort.h"
#include "InsertionSort.h"
#include "ShellSort.h"
#include "QuickSort.h"
#include "CommonFunction.h"
#include "HeapSort.h"
#include "MergeSort.h"
#define SIZE 10
int main() {
int array[SIZE], i, options;
srand(time(NULL));
for (i = ; i < SIZE; i++) {
array[i] = rand() / + ;
}
printf("The array of original sorting\n");
for (i = ; i < SIZE; i++) {
printf("%d ", array[i]);
}
printf("\nPlease choose your options:\n 1:BubbleSort\t 2:Selection\t ");
printf(
"3:InsertSort\t 4:ShellSort\t 5:QuickSort\t 6:HeapSort\t 7:MergeSort\t\n");
// scanf("%d", &options); for (i = ; i <= ; i++) {
options=i;
switch (options) {
case :
printf("The result of Bubble sorting is following:\n");
section4::bubbleSort(array, SIZE);
break;
case :
printf("The result of Selection sorting is following:\n");
section4::selectionSort(array, SIZE);
break;
case :
printf("The result of Insertion sorting is following:\n");
section4::insertionSort(array, SIZE);
break;
case :
printf("The result of Shell sorting is following:\n");
section4::shellSort(array, SIZE);
break;
case :
printf("The result of Quick sorting is following:\n");
section4::quickSort(array, , SIZE - );
section4::printfByStep(array, SIZE, SIZE);
break;
case :
printf("The result of Heap sorting is following:\n");
section4::heapSort(array, SIZE);
break;
case :
printf("The result of Merge sorting is following:\n");
section4::mergeSort(array, SIZE);
break;
} } // for (i = 0; i < SIZE; i++) {
// printf("%d ", array[i]);
// }
// printf("\n");
return ;
}
1、冒泡排序：
/*
* BubbleSort.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #pragma once
#include "CommonFunction.h"
namespace section4 {
/*
* 冒泡排序，很简单，相邻的两个元素进行比较，将较大的元素往后挪
* 每进行一次循环，排好一个元素
*/
void bubbleSort(int *a, int len) {
int i, j;
for (i = ; i < len; i++) {
for (j = ; j < len - i; j++) {
if (a[j] > a[j + ]) {
swap(&a[j],&a[j+]);
}
}
//The result of the %dth step
//section4::printfByStep(a,i,len);
}
section4::printfByStep(a,i,len);
} }
2、选择排序算法：
/*
* SelectionSort.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #pragma once
#include "CommonFunction.h"
namespace section4 {
/*
* @author
* 选择排序，每第i次循环为第i个位置找到此序列相应的第i个数。
*/
void selectionSort(int *a,int len){
int i,j,k;
for(i=;i<len;i++){
k=i;//记录此刻要数组中待排的位置
for(j=i;j<len;j++){
if(a[k]>a[j])
k=j;
}
if(k!=i){
section4::swap(&a[k],&a[i]);
}
//section4::printfByStep(a,i,len);
}
section4::printfByStep(a,i,len);
}
}
3、插入排序算法：
/*
* InsertionSort.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #pragma once
#include "CommonFunction.h"
namespace section4{
/*
* 此处的插入排序没有安排哨兵，即没有将a[0]空出来
*/
void insertionSort(int *a,int len){
int i,temp,j;
for(i=;i<len;i++){
temp=a[i];
j=i-;
while(j>=&&temp<a[j]){
a[j+]=a[j];
j--;
}
a[j+]=temp;
// section4::printfByStep(a,i,len);
}
section4::printfByStep(a,i,len);
}
}
4、希尔排序算法：
/*
* ShellSort.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/
#pragma once
#include "CommonFunction.h"
namespace section4 {
/*
* 希尔排序的思路是：每次以i/2的大小进行插入排序，第一次是以len/2的长度进行比较
* i为相隔的步长,每次以i的步长往前进行比较，直到步长为1。
*
*/
void shellSort(int *a, int len) {
int i, j, temp,k, x = ;
for (i = len / ; i >= ; i = i / ) {
for (j = i; j < len; j++) {
temp = a[j];
k = j - i;
while (temp < a[k] && k >= ) {
a[k + i] = a[k];
k = k - i;
}
a[k + i] = temp;
}
x++;
//section4::printfByStep(a, x, len);
}
section4::printfByStep(a, x, len);
}
}
5、快速排序算法：
/*
* QuickSort.h
*
* Created on: 2015年11月16日
* Author: hoojjack
*/ #pragma once
#include "CommonFunction.h"
namespace section4 {
/*@author
* 快速排序：这是自己按照快速排序的思路写的，刚开始出现两个地方的错误
* 1、递归循环的时候没有判断(left < low - 1)和(high + 1 < right)导致递归的时候
* 出现left值比right值大，以致递归不能结束
*
* 2、temp <= a[high] 没有判断=号，导致如果数组里出现相同的数字时，low和high的位置没有变化
* 导致循环不断地在交换a[low]和a[high]的值，出现死循环。
*
*/
void quickSort(int *a, int left, int right) {
int low, high, temp;
low = left;
high = right;
temp = a[low];
while (low < high) {
while (temp <= a[high] && low < high) {
high--;
}
a[low] = a[high];
while (temp >= a[low] && low < high) {
low++;
}
a[high] = a[low]; }
a[low] = temp;
// printf("low=%d,high=%d\n", low, high);
if (left < low - )
quickSort(a, left, low - );
if (high + < right)
quickSort(a, high + , right); } }
6堆排序算法：
/*
* HeapSort.h
*
* Created on: 2015年11月17日
* Author: hoojjack
*/ #pragma once
#include "CommonFunction.h" namespace section4 {
/*
* @author
* 堆排序应该注意的几点：
* 1、首先从最后一个父节点开始往上堆排序，在计算的时候考虑数组下标，计算
* 最后一个父节点的计算公式是len/2-1(因为数组从0开始编号)，然而在算它的孩子几点时
* 左孩子节点不再是2*parent，而是2*parent+1;
* 2、对数组进行从小到大排序，需要建立大根堆，因为数字大的排在数组后面
*/
void heapSort(int *a, int len) {
int child, parent, t, i, j, z;
for (i = ; i < len; i++) {
z = len - - i;
for (j = ((z + ) / ) - ; j >= ; j--) {
parent = j;
while (( * parent + ) <= z) {
child = * parent + ;
if ((child + ) <= z) {
if (a[child] > a[child + ]) {
t = child;
} else {
t = child + ;
}
} else {
t = child;
}
if (a[parent] < a[t]) {
section4::swap(&a[parent], &a[t]);
} else {
break;
}
}
}
section4::swap(&a[],&a[z]);
//section4::printfByStep(a,i,len);
}
section4::printfByStep(a,i,len);
} }
7、归并排序算法：
/*
* MergeSort.h
*
* Created on: 2015年11月17日
* Author: hoojjack
*/ #pragma once
#include<stdlib.h>
#include "CommonFunction.h"
namespace section4 {
/*
* @author
* 分步归并函数
*
*/
void mergeOne(int *a, int *b, int n, int len) {
int i, j, s, t, e, k;
s = ;
while (s < len) {
i = s;
t = n + s;
j = s + n;
e = s + * n - ;
k = s;
/*其中，i代表第一个归并子序列的首位，t代表此序列的末位
* j代表第二个归并子序列的首位，e代表此序列的末位
* k代表另一个数组的下标
* e的大小没有进行判断，容易导致最后一次归并时，
* 导致下标越界，故一定要判断e是否>=len
*/
if(e>=len){
e=len-;
}
while (i < t && j <= e) {
if (a[i] < a[j]) {
b[k++] = a[i++];
} else {
b[k++] = a[j++];
}
}
while (i < t) {
b[k++] = a[i++];
}
while (j <= e) {
b[k++] = a[j++];
}
//s在此刻第二个归并子序列e的基础前进1
s = e + ;
}
// if (s < len) {
// for (; s < len; s++)
// b[s] = a[s];
// }
}
/*
* 归并函数，b为开辟一个新数组的首地址，f为标志符，
* 当f=1时，将数组a中的数复制到数组b中,否则，进行相反操作
* s为每次归并的长度，1,2,2^2,2^3,......
* 直到数组子序列归并为一个，即s<len
*/
void mergeSort(int *a, int len) {
int *b;
int f = , s = , count = , h;
if (!(b = (int *) malloc(sizeof(int) * len))) {
printf("内存分配失败\n");
exit();
}
while (s < len) {
if (f == ) {
mergeOne(a, b, s, len);
// section4::printfByStep(b, count++, len);
} else {
mergeOne(b, a, s, len);
// section4::printfByStep(a, count++, len);
}
f = - f;
s = s * ; }
if (!f) {
for (h = ; h < len; h++)
a[h] = b[h];
}
section4::printfByStep(a, count, len);
free(b);
}
}
最后的结果是：
The array of original sorting Please choose your options:
:BubbleSort :Selection :InsertSort :ShellSort :QuickSort :HeapSort :MergeSort
The result of Bubble sorting is following:
The result of the 10th step The result of Selection sorting is following:
The result of the 10th step The result of Insertion sorting is following:
The result of the 10th step The result of Shell sorting is following:
The result of the 3th step The result of Quick sorting is following:
The result of the 10th step The result of Heap sorting is following:
The result of the 10th step The result of Merge sorting is following:
The result of the 0th step