这些天发现算法中的一些内容有点遗忘了，今晚又重新看了一下，这也难怪，在做的一些小项目中，其实算法用的并不是太多，很多都是别人封装好的。其实各种类库都是用了这些基本的算法再优化从而形成API供给程序员使用。所以，我一直觉得语言只是工具，而算法这些才是真正重要的东西，有了这些理论基础其实你使用任何语言都可以自行实现。
这几天在看搜索引擎的相关内容，对于其中的查找、索引也有了一定的了解，后期还需要加大这方面的学习。所以将自己复习排序相关的基本知识mark一下，以待自己后期进行查看。
排序简而言之就是对一些列的数据进行空间上的处理。分为内部排序和外部排序。而底下几种排序都属于内部排序的范畴。
以下的一系列的代码都是使用Java来实现，后期将会利用C/C++来实现一遍。
###冒泡排序
冒泡排序是一种特别简单的排序方式，其通过将最小的最轻的放在最上面从而得名。我们来举一串数字进行排序：
假设有一段要排序的数字为10,8,1,14,89,24,58。
则通过冒泡排序的方式排序过程如下所示：
第一次：10,8,1,14,89,24,58
10,8,1,14,24,89,58
10,8,1,14,24,89,58
10,1,8,14,24,89,58
1,10,8,14,24,89,58
我们看到第一趟排序已经把最下的数值1放到最前面了，下面我们还按照那样的规则进行排序，则最终会达到我们想要的顺序。
程序代码示例如下：
package com.test.sort;
//冒泡排序
public class BubbleSort {
static void bubbleSort(int[] numArray){
long start = System.nanoTime();
int sortLength = numArray.length;
int temp;
for(int i =1;i<=sortLength;i++){
for(int j=0;j<sortLength-i;j++){
if(numArray[sortLength-j-1]<=numArray[sortLength-j-2]){
temp = numArray[sortLength-j-2];
numArray[sortLength-j-2] = numArray[sortLength-j-1];
numArray[sortLength-j-1] = temp;
}
}
}
long end = System.nanoTime();
long countTime= end-start;
System.out.println("The used time is:"+countTime);
for(int k=0;k<sortLength;k++){
System.out.print(numArray[k]);
}
}
public static void main(String[] args) {
int a[] = {10,8,1,14,89,24,58};
bubbleSort(a);
}
}
程序打印出如下结果：
The used time is:3422
1,8,10,14,24,58,89
####不知道发现一个问题没有，例如我们爱第一趟中将1给找出来之后，我们进行第二次排序会发现有些原本排好的又会继续比较一次或者交换，这无疑对性能产生了影响，我们可以在程序中做如下改善：
package com.test.sort;
//冒泡排序
public class BubbleSort {
static void bubbleSort(int[] numArray){
long start = System.nanoTime();
int sortLength = numArray.length;
int temp;
boolean exchanged;
for(int i =1;i<=sortLength;i++){
exchanged = false;
for(int j=0;j<sortLength-i;j++){
if(numArray[sortLength-j-1]<=numArray[sortLength-j-2]){
temp = numArray[sortLength-j-2];
numArray[sortLength-j-2] = numArray[sortLength-j-1];
numArray[sortLength-j-1] = temp;
exchanged = true;
}
}
if (!exchanged){
break;
}
}
long end = System.nanoTime();
long countTime= end-start;
System.out.println("The used time is:"+countTime);
for(int k=0;k<sortLength;k++){
System.out.print(numArray[k]+",");
}
}
public static void main(String[] args) {
int a[] = {10,8,1,14,89,24,58};
bubbleSort(a);
}
} 添加的代码说明，判断是否两个值比较过，如果比较过我们就跳出循环。
####关于时间复杂度：
假如使用第一个没有进行判断的程序，我们会发现性能相当差，复杂度为O(n^2),而使用第二种方
式可以降低到O(n)。
###选择排序
选择排序也是一种性能极低的排序算法，它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。其实一种通过元素不断比较来形成排序。
我们可以来举个例子：假设要对10,8,1,14,89,24,58进行排序：
10,8,1,14,89,24,58
8,10,1,14,89,24,58
1,10,8,14,89,24,58
第一趟算是完成，底下还要进行第二趟。 我们看代码示例：
package com.test.sort;
//选择排序
public class SelectSort {
static void selectSort(int num[]){
int length = num.length;
int temp;
int min;
for(int index=0;index<length-1;index++){
min = index;
for(int j=index+1;j<length;j++){
if(num[j]<num[min]){
temp = num[j];
num[j] = num[min];
num[min] = temp;
}
}
}
for(int k=0;k<length;k++){
System.out.print(num[k]+",");
}
}
public static void main(String[] args) {
int a[] = {10,8,1,14,89,24,58};
selectSort(a);
}
} 运行结果如下：
1,8,10,14,24,58,89
关于时间复杂度：
可以通过分析此算法的时间复杂度为：O(n^2)。
###快速排序
快速排序是相对于前两个而言比较性能相对较高的排序算法。其通过分治法把一个序列分为连个子序列，以一个基点来判断两端数值的比较。
其基本步骤为：
1、从整个序列中挑选一个作为基准(pivote);
2、对序列进行排序，比基准大的放到它的右边，比基准小的放到它的左边，从而进行分区；
3、进行递归，把小于基准的和大于基准的序列再进行分区排序。
下面我们来看一段程序的实现：
package com.test.sort;
//快速排序
public class QuickSort {
static void qSort(int[] num,int low,int high){
if(low<high){
int povitePosition = partion(num,low,high);
qSort(num, low,povitePosition - 1);
qSort(num, povitePosition + 1 , high);
}
}
static int partion(int[] num,int low,int high){
int pivote = num[low];
while(low<high){
while(high>low&&(compare(pivote,num[high]))<=0){
high--;
}
num[low] = num[high];
while(high>low&&(compare(pivote,num[high]))>=0){
low++;
}
num[high] = num[low];
}
num[low] = pivote;
return low;
}
static int compare(int lNum,int hNum){
return lNum-hNum;
}
public static void main(String[] args) {
int[] a = {10,8,1,14,89,24,58};
qSort(a,0,a.length-1);
for(int i =0;i<a.length;i++){
System.out.println(a[i]);
}
}
}