冒泡,插入,希尔,选择,归并,快速,堆排序总结

冒泡排序

概念:依次比较相邻的两个数,小数放在前面,大数在后,若相反则交换。

第一趟(最大的数放在最后):首先比较第1个和第2个数,将小数放前,大 数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。

第二趟(第二大的数放在倒数第二):仍从第一对数开始比较,将小数放前,大数放后,一直比较到倒数第 二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。

如此下去,重复以上过 程,直至最终完成排序。每个循环体都是从第一个数开始和第二个数比较,只不过最终比较的范围在逐步缩小

void BubbleSort1(int a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 1; j < n – i; j++)
if (a[j – 1] > a[j])
Swap(a[j – 1], a[j]);
}

插入排序

概念:把序列分为有序区和无序区,每次把无序区第一个元素插入到有序区里进行排序,增加有序区,减小无序区,直到所有元素有序

(1) a[n]数组,a[0]为有序区,a[i….n-1]为无序区,此时i=1。

(2)  依次让a[i]插入到a[0…i-1]有序区中,从后往前比较,若有序区插入的前一个元素a[i-1]大于a[i],交换a[i-1]和a[i],类似冒泡排序第一趟,进行排序

(3)让每个a[i]都并入有序区(i++)

void Insertsort3(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i – 1; j >= 0 && a[j] > a[j + 1]; j–)
Swap(a[j], a[j + 1]);
}

希尔排序

概念:希尔排序是选定一个步长,一般是n/2,之后按照步长把序列分成几行,排序每列的值,然后展开,步长再减半重复这个步骤

比如[49,38,65,97,26,13,27,49,55,4],k=10/2=5,分成两行后:

    49 38 65 97 26

13 27 49 55 4

对每列排序:

    13 27 49 55 4

49 38 65 97 26

之后展开为[13,27,49,55,4,49,38,65,97,26],k=5/2=2,分成5行

    13 27

49 55

4 49

38 65

97 26

对每列排序:

 

4 26

13 27

38 49

49 55

97 65

之后展开[4,26,13,27,38,49,49,55,97,65] k=2/2=1,就可以用插入排序了

void shellsort3(int a[], int n)
{
int i, j, gap;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i – gap; j >= 0 && a[j] > a[j + gap]; j -= gap)
Swap(a[j], a[j + gap]);
}

直接选择排序

概念:类似直接插入排序,将数据分为有序区和无序区,区别是插入排序是从无序区取第一个元素直接插入有序区以形成一个更大的有序区,而选择排序是从无序区里选一个最小的元素直接放到有序区的最后(即最小的和无序区的第一个交换),在下一趟选择中,这个元素作为有序区的最后一个元素处理。

(1) 把数组全部初始状态看做无序区,即a[0…n-1],i=0;

(2) 在无序区a[i…n-1]中选取一个最小元素,将其与a[i]交换,换后形成a[0…i]有序区

(3)i++重复,知道i=n-1

3,4,1,5,2

1 | 4,3,5,2 //无序区最小的是1,和3换(3是无序区第一个)

1,2 |3,5,4 //1是有序区,然后无序区最小的是2,和4交换(4是无序区第一个)

1,2,3|5,4 //3和3自己交换,不变

1,2,3,4,5| //4和5交换

void Selectsort(int a[], int n)
{
int i, j, nMinIndex;
for (i = 0; i < n; i++)
{
nMinIndex = i; //找最小元素的位置
for (j = i + 1; j < n; j++)
if (a[j] < a[nMinIndex])
nMinIndex = j;
Swap(a[i], a[nMinIndex]); //将这个元素放到无序区的开头
}
}

归并排序

概念:归并的意思是递归拆解,把序列递归拆开到不能再拆,然后再归在一起重新排序,网上看了个比较好的详细原理解释:

“归并排序”。“归”代表的是递归的意思,递归的将数组折半的分离为单个数组,例如数组:[2,6,1,0],计算机会先折半,分为[2,6]和 [1,0],然后再折半将数组分离,分为[2],[6]和[1],[0]。那么 “并”是什么意思呢?其实“并”就是将分开的数据按照从小到大或者从大到小的顺序在放到一个数组中。如上面的[2],[6]合并到一个数组中是 [2,6],[1],[0]合并到一个数组中是[0,1],然后再将[2,6]和[0,1]合并到一个数组中即为[0,1,2,6]。

(1)先来看一下将两个数组合并成一个有序数组的原理。

两个数组,每一个数组内部都是有序的,比如:
a[5,7] 和 b[6,11,37]

我们申请足够大的空间,来放排好序的数组。比如这个数组叫 c[]。

每次取两个数组中最小的数,进行比较,小的取出放入 c[]。
如此将两个数组中的元素都取完,全部放入 c[],c[] 中就是一个有序的数组。比如:

第1次:5和6比较,5较小,所以 a[7], b[6,11,37] -> c[5]
第2次:7和6比较,6较小,所以 a[7], b[11,37] -> c[5,6]
第3次:7和11比较,7较小,所以 a[], b[11,37] -> c[5,6,7]
第4次:a[] 空了,所以 b[] 中剩下的都是排好序的大的,所以 a[], b[] -> c[5,6,7,11,37]

(2)然后再来看一下递归的产生有序数组。

每次:把一个无序数组,分成前后两半(根据数组中的元素个数,就可以确定到哪里是一半),首先对前一半进行递归调用,然后对后一半进行递归调用。最后归并,产生一个完整的有序数组。

比如:[7, 5, 37, 6, 11],

一共有5个元素,5/2=2,所以分成 [7,5] [37,6,11]。

对[7,5] 进行递归调用,一共有2个元素,2/2=1,所以分成 [7] [5]。
对[7] 进行递归调用,发现到头了,返回。
对[5] 进行递归调用,发现到头了,返回。
于是归并 [7] [5],得到有序数组 [5,7],返回。

对[37,6,11] 进行递归调用,一共有3个元素 3/2=1,所以分成 [37] [6,11]。
对[37] 进行递归调用,发现到头了,返回。

对[6,11] 进行递归调用,一共有2个元素 2/2=1,所以分成 [6] [11]。
对[6] 进行递归调用,发现到头了,返回。
对[11] 进行递归调用,发现到头勒,返回。
于是归并 [6] [11],得到有序数组 [6,11],返回。

于是归并 [37] [6,11],得到有序数组 [6,11,37],返回。

于是归并 [5,7] [6,11,37],得到有序数组 [5,6,7,11,37],返回。排序完成。

bool MergeSort(int a[], int n)
{
int *pTempArray = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n – 1, pTempArray);
delete[] pTempArray;
return true;
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
//将有二个有序数列a[first…mid]和a[mid…last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] < a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}

快速排序

概念:快速排序运用到分治法,A[0]……A[N-1],选用第一个数据A[0]作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序

1)设置两个变量I、J,排序开始的时候:I=0,J=N-1;

2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];

3)从J开始向前搜索,即由后开始向前搜索(J=J-1即J–),找到第一个小于key的值A[j],A[j]与A[i]交换;

4)从I开始向后搜索,即由前开始向后搜索(I=I+1即I++),找到第一个大于key的A[i],A[i]与A[j]交换;

5)重复第3、4、5步,直到 I=J;

例子:

示例:待排序的数组A的值分别是:(初始关键数据:key=49) 注意关键key永远不变,永远是和key进行比较,无论在什么位置,最后的目的就是把key放在中间,小的放前面大的放后面。

A[0] A[1] A[2] A[3] A[4] A[5] A[6]
49 38 65 97 76 13 27

进行第一次交换后:27 38 65 97 76 13 49   (从后面开始找,找到27和49交换,此时:J=6)

进行第二次交换后:27 38 49 97 76 13 65   ( 前面开始找>key的值,65>49,两者交换,此时:I=2 )

进行第三次交换后:27 38 13 97 76 49 65   ( 从后开始找,J=5)

进行第四次交换后:27 38 13 49 76 97 65   ( 从前面开始找大于key的值,97>49,两者交换,此时:I=3,J=5 )

此时再执行第三步的时候就发现I=J=3,从而结束一趟快速排序,那么经过一趟快速排序之后的结果是:27 38 13 49 76 97 65,即所有大于key49的数全部在49的后面,所有小于key(49)的数全部在key(49)的前面。

接着再分别对A[0~2]和A[4~6]进行快速排序

 

int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
int i = l, j = r;
int x = s[l]; //s[l]即s[i]
while (i < j)
{
// 从右向左找小于x的数来填s[i]
while(i < j && s[j] >= x)
j–;
if(i < j)
{
s[i] = s[j]; //将s[j]填到s[i]中
i++;
}
// 从左向右找大于或等于x的数来填s[j]
while(i < j && s[i] < x)
i++;
if(i < j)
{
s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
j–;
}
}
//退出时,i等于j。将x填到正确位置
s[i] = x;
return i;
}
//分治法的代码 :
void quick_sort1(int s[], int l, int r)
{
if (l < r)
{
int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
quick_sort1(s, l, i – 1); // 递归调用
quick_sort1(s, i + 1, r);
}
}

 堆排序

//to do

发表评论

电子邮件地址不会被公开。 必填项已用*标注