日本语  
 
  微信公众平台(ptsolution)
  大学IT相关专业查询
职位搜索:
在华知名日企名录

八大排序算法及实现

本文给出了八大排序算法的简单思路介绍以及代码实现(仅核心代码,程序中出现的drive函数为排序驱动程序)。

八大排序算法及实现

1. 插入排序

1)将一个元素插入到已经排好序的有序表中,从而使得有序表的个数+1。 算法从第二个元素开始。将一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

2) 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置以使得其变成有序的序列。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

void insertSort(int* a, int n)

{

int i, j, temp;

for( i = 1; i < n; i++ )

{

temp = a[i];

for( j = i - 1; j >= 0 && temp < a[j]; j-- )

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

a[j + 1] = temp;

}

}

2. 冒泡排序

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。也就是说在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

void bubbleSort(int* a, int size)

{

int i, j, temp;

for( i = 0; i < size - 1; i++ )

{

for( j = 0; j < size - i - 1; j++ )

{

if( a[j + 1] < a[j] )

{

temp = a[j];

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

a[j + 1] = temp;

}

}

}

}

3.选择排序

1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

3)重复第二步,直到所有元素均排序完毕。

void selectionSort(int* a, int size)

{

int min_index, min_value, i, j, temp;

for( i = 0; i < size - 1; i++ )

{

min_index = i;

min_value = a[i];