排序算法，除了冒泡排序，选择排序，还有什么排序？能...

zzkang0206

本帖最后由 xietansheng 于 2014-2-26 23:44 编辑

排序算法，除了冒泡排序，选择排序，还有什么排序？能不能举个例子怎么用？

张继鲁 · 张继鲁

还有折半查找方法，网上有很多例子，在这我只举个折半查找的例子：

class arrayTest3
{
public static void main(String[] args)
{
int[] arr={2,3,6,7,13,23,34};
int index=halfSeach_2(arr,3);
System.out.println("index="+index);
}
public static int getInde_2(int[] arr,int key){
int min,max,mid;
min=0;
max=arr.length-1;
while(min<=max){
mid=(min+max)>>1;//右移一位，相当于(min+mid)/2
if(key>arr[mid]){
min=mid+1;
}else if(key<arr[mid]){
max=mid-1;
}else
return mid;
}
return min;
}
/*
折半查找。提高效率，但是必须要保证该数组是有序的数组。
*/
public static int halfSeach(int arr[],int key){
int min,max,mid;
min=0;
max=arr.length-1;
mid=(min+max)/2;
while(arr[mid]!=key){
if(key>arr[mid]){
min=mid+1;
}
else if(arr[mid]<key){
max=mid-1;
}
if(min>max){
return -1;
}
mid=(min+max)/2;
}
return mid;
}

复制代码

梦里花-静 · 梦里花-静

快速排序、希尔排序、堆排序、插入排序、归并排序和基数排序等很多的，学这些算法的时候这是说了用法和复杂度。这些你可以在网上查查资料。下面给你一个快速排序的例子吧。
快速排序的基本思想：
通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。

public int getMiddle(Integer[] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] > tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] < tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}

复制代码

它的平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。

xu6148152 · xu6148152

梦里花-静发表于 2014-2-26 11:05
快速排序、希尔排序、堆排序、插入排序、归并排序和基数排序等很多的，学这些算法的时候这是说了用法和复杂 ...

程序不完整啊。还需要归并部分。

syw02014 · syw02014

本帖最后由 syw02014 于 2014-2-26 17:05 编辑

1、直接插入排序：直接插入排序(straight insertion sort)的做法是：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。

public static int[] insertSort(int[] arr)
{
for(int i=1; i<arr.length;i++)
{
for(int j=i;j>0;j--)
{
if(arr[j]<arr[j-1])
{
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j] =temp;
}
else
break;
}
}
return arr;
}

复制代码

2、折半插入排序折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
折半插入排序算法是一种稳定的排序算法，比直接插入算法明显减少了关键字之间比较的次数，因此速度比直接插入排序算法快，但记录移动的次数没有变，所以折半插入排序算法的时间复杂度仍然为O(n^2)，与直接插入排序算法相同。

public static int[] halfInsert(int[] arr)
{
for (int i=1;i<arr.length;i++) //从第二个元素开始，需要做n-1趟插入排序，第一个元素自成有序区
{
int temp=arr[i];// 暂存
//low和high分别指向有序区中的第一个和最后一个元素
int low=0;// 定义从第一个元素开始为有序区
int high=i-1;// 有序区的元素从一个开始逐渐增加
//寻找在有序区中插入的位置，最后使high<low，就找到插入的位置,为high+1；也是low的位置
while(low<=high)
{
int m=(low + high)/2;// 有序区的中间元素
if(temp<arr[m])//如果比中间的元素小，则插入位置在低半区
high=m-1;
else //否则，插入位置在高半区
low=m+1;
}
// 把从low开始以后或high+1以后的元素向后移动，插入
for(int j=i;j>low;j--)
arr[j]=arr[j-1];// 移动元素
arr[low]=temp;// 插入在合适的位置
}
return arr;
}

复制代码

3、快速排序:通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A，将A赋给A[j]；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

public static void quickSort(int[] arr, int low, int high)
{
p=get(arr,low,high);
quickSort(arr,low,p-1);
quickSort(arr,p+1,high);
}
public static int get(int[] arr,int low,int high)
{
compare=arr[low];
while(low<high)//无论如何置换, 被置换的都包含compare的值
{
while(low<high && arr[high]>=compare)
high--;
temp = arr[low]; //在 low<high 的情况下找到a[high]<compare并置换
arr[low] = arr[high];
arr[high] = temp;
while(low<high && arr[low]<=compare)
low++;
temp = arr[low];//在 low<high 的情况下找到a[low]>compare并置换
arr[low] = arr[high];
arr[high] = temp;
}
return low; //while(low==hight)停止循环, 并返回枢轴位置
}

复制代码

4、希尔排序(缩小增量法) 属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进：它通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
h = 3 * h +1
反过来程序需要反向计算h序列，应该使用
h=(h-1)/3

public static void shellSort(int[] arr) // 计算出最大的h值
{
int h=1;
while(h<=arr.length/3)
h=h*3+1;
while(h>0)
{
for(int i=h;i<arr.length;i+=h)
{
if(arr[i]<arr[i-h])
{
int tmp=arr[i];
int j=i-h;
while(j>=0&&arr[j]>tmp)
{
arr[j+h]=arr[j];
j-=h;
}
arr[j+h]=tmp;
}
}
h=(h-1)/3; // 计算出下一个h值
}
}

复制代码

syw02014 · syw02014

5、堆排序：堆积排序(Heapsort)是指利用堆积树（堆）这种资料结构所设计的一种排序算法，可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法，辅助空间为O(1)，最坏时间复杂度为O(nlog2n) ，堆排序的堆序的平均性能较接近于最坏性能。堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。

大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

public static void heapSort(int[] arr)
{
for(int i=0;i<arr.length;i++)
{
createMaxdHeap(arr,arr.length-i-1);
swap(arr, 0, arr.length-i-1);
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + "\t");
}
}
public static void createMaxdHeap(int[] arr, int lastIndex)
{
for(int i=(lastIndex-1)/2;i>=0;i--)
{
int k=i;// 保存当前正在判断的节点
while (2*k+1<=lastIndex) // 若当前节点的子节点存在
{
int biggerIndex=2*k+1; // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
if(biggerIndex<lastIndex)// 若右子节点存在，否则此时biggerIndex应该等于 lastIndex
if(arr[biggerIndex]<arr[biggerIndex+1])// 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值
biggerIndex++;
if(arr[k] < arr[biggerIndex]) // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
{
swap(arr, k, biggerIndex);
k = biggerIndex;
}
else
break;
}
}
}
public static void swap(int[] arr, int i, int j)
{
if(i==j)
return;
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}

复制代码

6、归并排序
归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。归并排序算法稳定，数组需要O(n)的额外空间，链表需要O(log(n))的额外空间，时间复杂度为O(nlog(n))，算法不是自适应的，不需要对数据的随机读取。
工作原理：
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾

public static void mergeSort(int[] arr)
{
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int left, int right)
{
if(left>=right)
return;
int center=(left+right)/2; // 找出中间索引
sort(arr,left,center);// 对左边数组进行递归
sort(arr,center+1,right); // 对右边数组进行递归
merge(arr,left,center,right);// 合并
for(int i=0;i<arr.length;i++)
System.out.print(arr[i] + "\t");
}
/*
将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
arr:数组对象
left:左数组的第一个元素的索引
center:左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
right:右数组最后一个元素的索引
*/
public static void merge(int[] arr, int left, int center, int right)
{
int[] tmpArr = new int[arr.length];// 临时数组
int mid = center + 1;// 右数组第一个元素索引
int third = left; // third 记录临时数组的索引
int tmp = left;// 缓存左数组第一个元素的索引
while(left<=center&&mid<=right)
{
if(arr[left]<=arr[mid]) // 从两个数组中取出最小的放入临时数组
tmpArr[third++]=arr[left++];
else
tmpArr[third++]=arr[mid++];
}
while(mid<=right) // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
tmpArr[third++]=arr[mid++];
while(left<=center)
tmpArr[third++] = arr[left++];
while(tmp<=right)// 将临时数组中的内容拷贝回原数组中（原left-right范围的内容被复制回原数组）
arr[tmp]=tmpArr[tmp++];
}

复制代码

7、基数排序
基数排序已经不再是一种常规的排序方式，它更多地像一种排序方法的应用，基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键字进行排序，也就是说，基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字......然后，根据子关键字对待排序数据进行排序。
多关键字排序时有两种解决方案：
最高位优先法（MSD）(Most Significant Digit first)
最低位优先法（LSD）(Least Significant Digit first)
例如，对如下数据序列进行排序。
192,221,12,23
可以观察到它的每个数据至多只有3位，因此可以将每个数据拆分成3个关键字：百位（高位）、十位、个位（低位）。如果按照习惯思维，会先比较百位，百位大的数据大，百位相同的再比较十位，十位大的数据大；最后再比较个位。人得习惯思维是最高位优先方式。
对于多关键字排序来说，程序将待排数据拆分成多个子关键字后，对子关键字排序既可以使用桶式排序，也可以使用任何一种稳定的排序方法。

public static void radixSort(int[] arr,int radix,int d)
{
int[] tmp=new int[arr.length];// 缓存数组
int[] buckets=new int[radix];// buckets用于记录待排序元素的信息,buckets数组定义了max-min个桶
for(int i=0,rate=1;i<d;i++)
{
Arrays.fill(buckets,0); // 重置count数组，开始统计下一个关键字
System.arraycopy(arr, 0,tmp,0,arr.length); // 将data中的元素完全复制到tmp数组中
for(int j=0;j<arr.length;j++) // 计算每个待排序数据的子关键字
{
int subKey=(tmp[j]/rate)%radix;
buckets[subKey]++;
}
for(int j=1;j<radix;j++)
buckets[j]=buckets[j]+buckets[j-1];
for(int m=arr.length-1;m>=0;m--)// 按子关键字对指定的数据进行排序
{
int subKey=(tmp[m]/rate)%radix;
arr[--buckets[subKey]]=tmp[m];
}
rate *= radix;
}
}

复制代码

帐号		自动登录	找回密码
密码			加入黑马

排序算法，除了冒泡排序，选择排序，还有什么排序？能...

评分

6 个回复

点评

评分

评分

评分

黑马骑士勋章