Some_sort_algorithms

复习下数据结构常用的排序算法，更多内容上wiki

快速排序（不稳定 O(n log n)）

快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。百度百科

C代码:

(quicksort.c) download

#include "vell001.h"

#define NUM 20

// 对a的[low, high]区间分成两个区，返回分界点

int Partition(int* a, int low, int high){

  int key = a[low]; // 划分的关键点

  while(low < high){

      while(low < high && a[high] >= key) --high; // 找到比关键点小的节点

      a[low] = a[high]; // 把小节点放到左边

      while(low < high && a[low] <= key) ++low; // 找到比关键点大的节点

      a[high] = a[low]; // 把小节点放到右边

  }

  a[low] = key; // 最后把关键点放到分界点

  return low;

}

// 对a的[low, high]区间进行快速排序

int* QSort(int* a, int low, int high){

  if(low < high){

      int p = Partition(a, low, high);

      QSort(a, low, p-1); // 递归的对左分区快排

      QSort(a, p+1, high); // 递归的对右分区快排

  }

}

int* QuickSort(int* a, int n) {

  return QSort(a, 0, n-1);

}

void main() {

  int* a = GetRandomNum(NUM);

  PrintList(a, NUM);

  QuickSort(a, NUM);

  PrintList(a, NUM);

}

Java代码:

package arithmetic;

public class QuickSort {

  public static void main(String[] args) {

      int[] a = {6,5,42,3,2,4,67,7,2,9,4};

      a = sort(a, 0, a.length-1);

      for(int i=0; i<a.length; i++){

          System.out.print(a[i] + "  ");

      }

      System.out.println();

  }

  public static int[] sort(int[] a, int low, int high){

      if(low < high){

          int p = partition(a, low, high);

          sort(a, low, p-1);

          sort(a, p+1, high);

      }

      return a;

  }

  public static int partition(int[] a, int low, int high){

      int key = a[low];

      while(low < high){

          while(low < high && a[high] >= key) high--;

          a[low] = a[high];

          while(low < high && a[low] <= key) low++;

          a[high] = a[low];

      }

      a[low] = key;

      return low;

  }

}

2014-03-24 23:22:02

冒泡排序（稳定 O(n2)）

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。百度百科

C代码:

(bubblesort.c) download

#include "vell001.h"

#define NUM 20

int* BubbleSort(int* a, int n){

  int i = 0, j = 0, flag = 1, cup = 0;

  for(i=n-1; i>0 && flag; i--){

      flag = 0; // 设置一个标记，当顺序已经排好后不再运行

      for(j=0; j<i; j++){

          if(a[j] > a[j+1]){

              cup = a[j];

              a[j] = a[j+1];

              a[j+1] = cup;

              flag = 1;

          }

      }

  }

  return a;

}

void main(){

  int* a = GetRandomNum(NUM);

  PrintList(a, NUM);

  BubbleSort(a, NUM);

  PrintList(a, NUM);

}

2014/3/23 11:58:29

希尔排序（不稳定 O(n log n)）

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止百度百科

C代码:

(shell_sort.c) download

#include "vell001.h"

#define NUM 20

int* ShellSort(int* a, int n){

  int i = 0, j = 0, d = n, cup = 0;

  for(d=n/2; d>=1; d=d/2){ // 增量d为上次增量的一半，初始增量为总长度的一半

      for(i=d; i<n; i++){ // 分出来的所有组进行插入排序

          cup = a[i];

          for(j=i-d; j>=0 && a[j]>cup; j=j-d){

              a[j+d] = a[j];

          }

          a[j+d] = cup;

      }

  }

  return a;

}

void main(){

  int* a = GetRandomNum(NUM);

  PrintList(a, NUM);

  ShellSort(a, NUM);

  PrintList(a, NUM);

}

2014/3/23 13:20:05

堆排序（不稳定 O(n log n)）

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录百度百科

c代码:

(heap_sort.c) download

#include "vell001.h"

#define NUM 15

// 保证i位置为堆中最大的节点

// a:待调整堆数组，n:数组长度, i:待调整元素位置

int* HeapAdjust(int* a, int n, int i){

  int child, cup;

  // i: 父节点位置，child: 子节点位置（左:2*i+1,右:2*i+2）

  for(cup = a[i], child=2*i+1; child<n; i=child, child=2*i+1){

      // 如果右节点大于左节点child指向右节点

      if(child < n-1 && a[child+1] > a[child]) child++;

      // 如果子节点大于父节点则交换，并继续查找下一个节点（把当前的子节点当成新的父节点）

      if(a[child] > cup){

          a[i] = a[child];

          a[child] = cup;

      } else

          break; //如果不大于，则退出

  }

  return a;

}

// a:待调整堆数组，n:数组长度

int* HeapSort(int* a, int n){

  int cup, i;

  // 初始化堆，即对所有的非叶子节点进行HeapAdjust

  for(i = n/2; i>=0; i--){

      HeapAdjust(a, n, i);

  }

  // 把堆顶节点（最大节点）和堆中最后一个节点交换，然后对堆中除最后一个节点外的其他节点进行HeapAdjust

  for(i = n-1; i>0; i--){

      cup = a[i];

      a[i] = a[0];

      a[0] = cup;

      HeapAdjust(a, i, 0);

  }

  return a;

}

void main(){

  int* a = GetRandomNum(NUM);

  PrintList(a, NUM);

  HeapSort(a, NUM);

  PrintList(a, NUM);

}

2014-03-24 23:54:03

归并排序（稳定 O(n log n) 需要O(n)额外空间）

归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。wiki

c代码:

(merge_sort.c) download

#include "vell001.h"

#define NUM 20

// 合并a1,a2数组

void Merge(int* a1, int n1, int* a2, int n2) {

  int i, j, k;

  int* cup = (int*) malloc((n1+n2) * sizeof(int));

  // 按先放小数再放大数原则归并

  for(i=0, j=0, k=0; i<n1 && j<n2; k++) {

      if(a1[i] > a2[j]) {

          cup[k] = a2[j];

          j++;

      } else {

          cup[k] = a1[i];

          i++;

      }

  }

  // 将可能剩下的数直接放到结尾

  while(i<n1) cup[k++] = a1[i++];

  while(j<n2) cup[k++] = a2[j++];

  // 把归并好的cup数组全部复制给a1

  for(i=0; i<n1+n2; i++) a1[i] = cup[i];

  // 释放cup

  free(cup);

}

void MergeSort(int*a, int n) {

  if(n > 1){

      // 二分a数组

      int n1 = n / 2, n2 = n - n1;

      int* a1 = a, a2 = a + n1;

      MergeSort(a1, n1); // 递归排好左边

      MergeSort(a2, n2); // 递归排好右边

      Merge(a1, n1, a2, n2); // 归并两边

  }

}

void main() {

  int* a = GetRandomNum(NUM);

  PrintList(a, NUM);

  MergeSort(a, NUM);

  PrintList(a, NUM);

}

2014-03-25 15:48:58

vell001.h (我的小工具库)

(vell001.h) download

#include <stdio.h>

#include <time.h>

//获取n个0～n的随机数

int* GetRandomNum(int n) {

  srand( (unsigned)time( NULL ) );

  int* a = (int*)malloc(n * sizeof(int));

  int i = 0;

  for(i=0; i<n; i++) {

      a[i] = rand() % n;

  }

  return a;

}

// 打印数组

void PrintList(int* a, int n){

  int i = 0;

  for(i=0; i<n; i++){

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

  }

  printf("\n");

}

原文地址:
http://vblog.vell001.ml/2014/03/24/some-sort-algorithms.html

written by VellBibi
posted at http://vblog.vell001.ml

秒客网

Some_sort_algorithms

快速排序（不稳定 O(n log n)）

C代码:

Java代码:

冒泡排序（稳定 O(n2)）

C代码:

希尔排序（不稳定 O(n log n)）

C代码:

堆排序（不稳定 O(n log n)）

c代码:

归并排序（稳定 O(n log n) 需要O(n)额外空间）

c代码:

vell001.h (我的小工具库)

Some_sort_algorithms

快速排序（不稳定 O(n log n)）

C代码:

Java代码:

冒泡排序 （稳定 O(n2)）

C代码:

希尔排序（不稳定 O(n log n)）

C代码:

堆排序（不稳定 O(n log n)）

c代码:

归并排序（稳定 O(n log n) 需要O(n)额外空间）

c代码:

vell001.h (我的小工具库)

冒泡排序（稳定 O(n2)）