J2SE I一一有多少你不知道的数据排序？
前言
排序，三大查找是《数据结构》当中非常基础的知识点，在这里为了复习顺带总结了一下常见的排序算法。
常用比较排序算法的性能：
一、插入排序
基本思想：在一个已经排好序的序列中，将未被排序的元素按照原先序列的排序规则插入到序列中的指定位置。
常用举例：直接插入排序
直接插入排序（Straight Insertion Sorting）是一种简单的排序算法，他的基本思想是依次将每个记录插入到一个已经排好序的有序表中去，从而得到一个新的、记录增加1的有序表。具体过程如下：
初始序列：{45 38 66 90 88 10 25 }
第一步对前两个数进行排序，把38插入到45之前，得到新的序列{45 38 66 90 88 10 25}
第二步对前三个数进行排序，把66插入到有序序列{45 38}的合适位置，即{45 38 66 90 88 10 25}
以后的步骤是在都是在以上基础上的一个递归过程知道最后一个数25插入到合适的位置得到最终序列{10 25 38 45 66 88 90}
算法描述：
<span style="font-family:KaiTi_GB2312;font-size:18px;">
void StraightInsertSort(List R,int n)
//对顺序表R进行直接插入排序
{
int i, j;
for (i=2;i<=n;i++)//n为表长，从第二个记录起进行插入
{
R[0] = R[i];//第i个记录复制为岗哨
j = i - 1;
while (R[0].key<R[j].key)//与岗哨比较，直至键值不大于岗哨值
{
R[j +1]=R[j];//将第j个记录赋值给第j+1个记录
j--;
}
R[j + 1] = R[0];//将第i个记录插入的序列中
}
}</span>
二、交换排序
基本思想：比较两个记录的键值大小，如果两个记录键值的大小出现逆序，则交换这两个记录，这样将键值较小的记录向序列前部移动，键值较大的记录向序列后部移动，最终将得到有序序列。
（1）冒泡排序
冒泡排序法（Bubble Sorting）首先将第一个记录的键值和第二个记录的键值进行比较，若为逆序则将这两个记录交换，然后继续比较第二个和第三个记录的键值。以此类推，直到完成第n-1个记录和第n个记录的键值比较交换为止。这时便完成了第一趟气泡，其结果是将最大的记录移到最后一位。然后第二次气泡跟第一次类似，其结果是将第二大的记录移到倒数第二位。重复以上过程，直到整个排序过程终止得到最终有序序列。
<span style="font-family:KaiTi_GB2312;font-size:18px;">
void BubbletSort(List R,int n)
{
int i, j,temp,endsort;
for (i=1;i<=n-1;i++)
{
endsort = 0;
for (j = 1; j <= n - i - 1; j++)
{
if (R[j].key>R[j+1].key)//若为逆序则交换记录
{
temp = R[j];
R[j] = R[j + 1];
R[j + 1] = temp;
endsort = 1;
}
}
if (endsort == 0) break;
}
}</span>
### （2）快速排序
快速排序（Quick Sorting）是对冒泡排序的一种改进。它的基本思想是在n个记录中取某一个记录的键值为标准，通常取第一个记录键值为基准，通过一趟排序将待排序的记录分为小于等于这个键值和大于这个键值的两个独立的部分，这时前面部分的记录键值均比后面的记录键值小，然后对这两部分分别按照这种方法排序，直到获得整个有序序列。
算法描述：
<span style="font-family:KaiTi_GB2312;font-size:18px;">
//第一趟快速排序算法
int QuickPartition(List R,int low,int hign)
{
x=R[low]//赋初值，标准数
while (low < hign)
{
while ((low <hign) && (R[hign].key>=x.key )) hign--;
R[low]=R[hign];//自尾端进行比较，将比x小的记录移到低端
while ((low <hign) && (R[low].key<=x.key )) low++;
R[hign]=R[low];//自首端进行比较，将比x大的记录移到高端
}
R[low]=x;//第一趟排序结束，将x移到其最终位置
return low ;
}</span>
三、选择排序
基本思想：每次在n-i+1（i=1,2,3……，n-1）个记录中选取键值最小的记录作为有序序列的第i个记录。
常用举例：直接选择排序、堆排序。
（1）直接选择排序
直接选择排序（Selection Sorting）的基本思想是在第i次选择操作中，通过n-i次键值比较，从n-i+1个记录中选出最小的记录，并和第i(1<=i<=n-1)个记录交换。
算法描述：
<span style="font-family:KaiTi_GB2312;font-size:18px;">
void SelectSort(List R,int n)
{
int min, i, j;
for(i=1;i<=n-1;i++)//每次循环选择出最小一个键值
{
min=i;//假设第i个记录键值最小
for(j=i+1;j<=n;j++)
{
if(R[j].key<R[min].key) min =j;//记录下键值最小记录的下标
if(min!=i) swap(R[min],R[i]);//将最小键值记录和第i个记录交换
}
}
}</span>
（2）堆排序
堆排序（Heap Sorting）是利用堆的数据结构所设计的一种排序算法，可利用数组的特点快速定位指定索引的元素。堆分为最大堆和最小堆，最大堆中的任一节点的值都不小于它的两个孩子的值（若存在孩子的话）；最小堆则任一节点的值都不大于它的两个孩子的值。
算法描述：
<span style="font-family:KaiTi_GB2312;font-size:18px;">
void Sift(List R,int k,int m)
{
int i, j, x;
List t;
i = k; j = 2 * i;
x = R[k].key;
t = R[k];
while (j<=m)
{
if ((j < m) && (R[j].key > R[j + 1].key))
j++;//若存在右子树且右子树的关键字小，则沿右分支筛选
if (x < R[j].key) break;//筛选完毕
else
{
R[i] = R[j];
i = j;
j = 2 * i;
}
R[i] = t;//填入适当位置
}
}
//堆排序算法
void HeapSort(List R)
{
int i;
for (i = n / 2; i >= 1; i--)
Shit(R, i, n);//从第n/2个记录开始进行筛选建堆
for (i=n;i>=2;i--)
{
swap(R[1], R[i]);//将堆顶记录和堆中最后一个记录互换
Sift(R, 1, i - 1);//调整R[1]使R[1],……,R[i-1]变成堆
}
}</span>
四、归并排序
基本思想：
1）将已经有序的子序列合并，得到完全有序的序列，
2）先使每个子序列有序，再使子序列段间有序
3）若将两个有序表合并成一个有序表称为二路归并
常见举例：
二路归并排序。
二路归并排序是将两个有序表结合成一个有序表，基本思想是假设序列中有n个记录，可看成是n个有序的子序列，每个序列的长度为1.首先将每相邻的两个记录合并，得到n/2（向上取整）个较大的有序序列，每个子序列包含2个记录，再将上述子序列两两合并，得到（n/2）/2（向上取整）个有序序列，如此反复，知道得到最终有序序列为止。
步骤：
a 申请空间，让他大小为两个已经排序的序列之和，
该空间用来存放合并后的序列
b 设定两个指针，最初位置分别为两个已经排序序列起始位置
c 比较两个指针所指向的元素，选择相对较小的放入合并空间，并移动
指针到下一个位置
d 重复步骤c 知道某个指针达到序列尾
e 将另一个序列剩下的所有元素直接复制到合并序列尾。
//归并排序
void Merge(int a[], int left, int mid,int right)
{
int size = right - left + 1;
int *temp = (int *)malloc(size*sizeof(int));
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right)
{
temp[index++] = a[i] < a[j] ? a[i++] : a[j++];
}
while (i <= mid)
{
temp[index++] = a[i++];
}
while (j <= right)
{
temp[index++] = a[j++];
}
for (int k = 0; k < size; k++)
{
a[left++] = temp[k];
}
}
void MergeSort(int a[], int left, int right)
{
if (left == right) return;
int mid = left + ((right - left) >> 1);
MergeSort(a, left, mid);
MergeSort(a, mid + 1, right);
Merge(a, left, mid, right);
}
五.基数排序
基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。
分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[ ]
对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束
看到这里属实不容易了，点亮小心心喔~
