阅读目录
- 分类及比较
- 冒泡排序
- 快速排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 堆排序
1.分类及比较
排序 比较.jpg
2.冒泡排序
基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。
过程:
- 比较相邻的两个数据，如果第二个数小，就交换位置。
- 从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
- 继续重复上述过程，依次将第2.3...n-1个最小数排好位置。
代码:
void BubbleSort(int *pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=Count-1;j>i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp=pData[j-1];
pData[j-1]=pData[j];
pData[j]=iTemp;
}
}
}
}
优化: 略
3.快速排序
基本思想:
- 先从数列中取出一个数作为key值；
- 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
- 对左右两个小数列重复第二步，直至各区间只有1个数。
代码:
public static int[] qsort(int arr[],int start,int end) {
int pivot = arr[start];
int i = start;
int j = end;
while (i<j) {
while ((i<j)&&(arr[j]>pivot)) {
j--;
}
while ((i<j)&&(arr[i]<pivot)) {
i++;
}
if ((arr[i]==arr[j])&&(i<j)) {
i++;
} else {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i-1>start) arr=qsort(arr,start,i-1);
if (j+1<end) arr=qsort(arr,j+1,end);
return (arr);
}
public static void main(String[] args) {
int arr[] = new int[]{3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
int len = arr.length-1;
arr=qsort(arr,0,len);
for (int i:arr) {
System.out.print(i+"\t");
}
}
4.选择排序
基本思想:
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
代码:
void SelectSort(int *a, int len){
int tmp;
for(int i=0; i<len-1; i++){
int k=i;
for(int j=i+1; j<len; j++){
if(a[j]<a[k])
k=j;
}
if(k!=i){
tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
}
}
5.插入排序
基本思想:
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码:
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j= i-1;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-1]; //先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正确位置
}
}
}
6.希尔排序
基本思想:
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
代码:
/**
* 直接插入排序的一般形式
*
* @param int dk 缩小增量，如果是直接插入排序，dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j = i-dk;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-dk]; //首先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插入到正确位置
}
print(a, n,i );
}
}
/**
* 先按增量d（n/2,n为要排序数的个数进行希尔排序
*
*/
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
7.归并排序
基本思想:
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
首先考虑下如何将2个有序数列合并。这个非常简单，只要从比较2个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
略
8. 堆排序
略
