python实现冒泡排序算法的非递归版本_算法基础：6种经典排序算法的递归和非递归实现...

本文的算法实现主要参考两本书：

《算法导论》

《大话数据结构》

接口

#ifndef _SORT_H

#define _SORT_H

#define true 1

#define false 0

typedef int bool;

typedef int elem_t;

typedef struct{

elem_t *a;

int len;

} List;

void printlist(elem_t *a, int n, int sps);

bool listCompare(List *a1, List *a2,int n);

// ==============常用内部排序=================

// 冒泡排序(简单交换排序的改进)

extern void bubbleSort_RE(elem_t *a, int len);

extern void bubbleSort_NRE(elem_t *a, int len);

// 选择排序

extern void selectionSort_RE(elem_t *a, int n);

extern void selectionSort_NRE(elem_t *a, int n);

// 插入排序

extern void insertionSort_RE(elem_t *a, int n);

extern void insertionSort_NRE(elem_t *a, int n);

// 希尔排序(插入排序的改进)

extern void shellSort_RE(elem_t *a, int n);

extern void shellSort_NRE(elem_t *a, int n);

// 堆排序(简单选择排序的改进)

extern void heapSort_RE(elem_t *a, int n);

extern void heapSort_NRE(elem_t *a, int n);

// 归并排序

extern void mergeSort_RE(elem_t *a, int n);

extern void mergeSort_NRE(elem_t *a, int n);

// 快速排序(冒泡排序的改进)

extern void quickSort_RE(elem_t *a, int n);

extern void quickSort_NRE(elem_t *a, int n);

#endif

测试代码

注意

NRE表示非递归版本，RE表示递归版本

部分排序算法提供了两种版本的实现

// test_sort.c

#include "sort.h"

#include

#include

#include

#include

static const int n = 50;

static const int sps = 10;

int main(){

List list;

list.a = (elem_t *)malloc(sizeof(int)*n);

list.len = n;

printf("Random Number From 0 ~ %d\n", list.len);

srand(time(0));

for (int i = 0; i < list.len; ++i)

{

list.a[i] = rand() % list.len;

printf("%d", list.a[i]);

(i+1) % sps == 0 ? printf("\n") : printf("\t");

}

// bubbleSort_RE(list.a,list.len); // test pass

// bubbleSort_NRE(list.a,list.len); // test pass

// selectionSort_RE(list.a,list.len); // test pass

// selectionSort_NRE(list.a,list.len); // test pass

// insertionSort_RE(list.a,list.len); // test pass

// insertionSort_NRE(list.a,list.len); // test pass

// shellSort_NRE(list.a,list.len); // test pass

// heapSort_NRE(list.a,list.len); // test pass

// mergeSort_RE(list.a,list.len); // test pass

quickSort_RE(list.a,list.len); // test pass

printf("\nOrdered Sequence:\n");

printlist(list.a, list.len, sps);

free(list.a);

exit(0);

}

接口的实现

#include "sort.h"

#include

#include

#include

// #include

// used for heapSort

#define PARENT(i) (i >> 1)

#define LEFT(i) (i << 1)

#define RIGHT(i) (i << 1 + 1)

static const int MAX_INT = ((unsigned)(-1))>>1;

// static const int MIN_INT = ~MAX_INT;

static inline int Parent(int i) {return i >> 1;}

static inline int Left(int i) {return i << 1;}

static inline int Right(int i) {return ((i << 1) + 1);}

// declaration of inner function

static int elemCompare(elem_t a, elem_t b);

static void swap(elem_t *a, int i, int j);

static bool makeMinToBeHead_BUB(elem_t *a, int n);

static void makeMinToBeH