用Java实现 一些口试要求的基本的排序算法
用Java实现 一些面试要求的基本的排序算法
归并排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
首先是插入排序：
个人思路：插入排序就是将一个无序的数组，从第一个开始，将下一个数插入到前面的有序数组中，使之前的数组依然有序。（我说的比较白话，因为是自己总结的）
比如数组 {1,5,3,4,5,8,2}，从第二个开始，跟前面的数比较，如果小于前面的数，则交换。所以步骤如下：
{1,5,3,4,5,8,2}-->{1,3,5,4,5,8,2}-->{1,3,4,5,8,2}-->{1,3,4,5,8,2}-->{1,3,4,5,2,8}-->{1,3,4,2,5,8}-->{1,3,2,4,5,8}-->{1,2,3,4,5,8}，最后排序完成。
算法实现为：
public class InsertSort {
public static void main(String []args){
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
insertSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static void insertSort(int []a){
//从第二位开始
for(int i=1;i<a.length;i++){
//判断j是否大于零，这样避免a[j-1]越界
//从i开始，依次找前面的数，如果a[j]<a[j-1]（后面的数大于前面的数），
//则做交换，并且j--。 如果a[j]>a[j-1]，则说明已经到了正确的位置，结束for循环
for(int j=i;j>0&&(a[j]<a[j-1]);j--){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
希尔排序：希尔排序是先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。算法实现如下：
public class ShellSort {
public static void main(String[] args) {
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
shellSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static void shellSort(int a[]){
//i是增量的值
for(int i=a.length/2;i>2;i/=2){
//将前i个属于总量为i的不同分组做插入排序
for(int j=0;j<i;j++){
insertSort(a,j,i);
}
}
insertSort(a,0,1);
}
public static void insertSort(int a[],int start,int inc){
//从start开始没意义，所以从第二个属于inc增量的组的开始算
for(int i=start+inc;i<a.length;i+=inc){
//用插入排序对其进行排序 当j>=inc时，是因为最小j就为inc，如果比inc还小，则会越界
for(int j=i;j>=inc&&(a[j]<a[j-inc]);j-=inc){
int temp = a[j];
a[j] = a[j-inc];
a[j-inc] = temp;
}
}
}
}
堆排序： 堆排序是用数组来表示一个完全二叉树。 具体思路就不写了，在算法代码中我直接用注释说明，原理大家找下资料就可以了
public class HeapSort {
//本人用的是大根堆
public static void main(String[] args) {
int a[] = {1,5,3,4,5,8,10,21,4,50,100,5,1};
heapSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
//moveDown主要是用来将子树初始化，first相当于当前子树的根，last是最后一个节点的位置
public static void moveDown(int a[],int first,int last){
//得到左子树 因为数组是从零开始，所以需要加一
int largest = 2*first+1;
while(largest<=last){//largest可以等于largest因为最后一位也可能是最大值，不能去除
//这个循环是为了找到最大节点的位置
//largest记录着当前最大节点的位置
while(largest<last&&(a[largest]<a[largest+1])) largest++;
//找到最大的位置，判断是否比first处的值大，大的话，交换值，同时因为移动了子树的节点
//largest为根的子树的堆混乱了，需要重新建堆，所以将根first设为largest
//largest依旧取根的左子树
//如果小的话，则说明根处的值已经是最大的了，跳出循环
if(a[first]<a[largest]){
int temp = a[first];
a[first] = a[largest];
a[largest] = temp;
first = largest;
largest = 2*first+1;
}else{
largest = last+1;
}
}
}
public static void heapSort(int a[]){
//i=a.length/2-1，得到最后一个叶子节点的父亲，从最后的一个子树开始进行建堆
for(int i=a.length/2-1;i>=0;i--){
moveDown(a,i,a.length-1);
}
//从最后一个开始，依次将最大的数交换到最后，
for(int i=a.length-1;i>0;i--){
int temp = a[0];
a[0] = a[i];
a[i] = temp;
//然后在将堆重新构造
moveDown(a,0,i-1);
}
}
}
冒泡排序：最基本的排序，基本上大家都会0 0，就是依次选第i位（i<n），并从后面开始，将i后的最小的数冒到第i位。
算法实现：
public class maopao {
public static void main(String []args){
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
mao(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static void mao(int a[]){
//i从0开始
for(int i=0;i<a.length;i++){
//从最后一位开始，如果小于前面的数，则交换
for(int j=a.length-1;j>i;j--){
if(a[j]<a[j-1]){
int temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
}
选择排序：
数组从i（0<i<n）开始，需要一个辅助数据，temp，存储i之后的最小的数的位置，如果选择之后，temp！=i，则交换temp和i的数，i++；
算法如下：
public class SelectSort {
public static void main(String []args){
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
selectSort(a);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
public static void selectSort(int a[]){
//存储当前最小的数的位置
int temp;
for(int i=0;i<a.length;i++){
//temp刚开始为i
temp = i;
for(int j=i+1;j<a.length;j++){
//如果存在比他小的数，则temp=j
if(a[temp]>a[j]){
temp = j;
}
}
//如果temp！=i，说明后面有比i位上的数更小的数
//交换temp和i位的数
if(temp!=i){
int t = a[i];
a[i] = a[temp];
a[temp] = t;
}
}
}
}
快排： 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
算法如下：
public class quickSort {
public static void main(String[] args) {
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
quickSort(a,0,a.length-1);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
//得到中间位置，这个位置的前面的数都小于他，后面的数都大于他
public static int partition(int a[],int low,int high){
//以low处为基准点
int paior = a[low];
while(low<high){
//从后看，如果high大于等于基准点，则high--
while(low<high&&a[high]>=paior) high--;
//这个时候high处的值小于等于基准点，将值付给low
a[low] = a[high];
//从前面看，如果low小于基准点的值，则low++
while(low<high&&a[low]<=paior) low++;
//这个时候low处的值大于等于基准点，将值付给high
a[high] = a[low];
}
//最后将low处附上基准点的值，low就是基准点的位置，返回low
a[low] = paior;
return low;
}
public static void quickSort(int a[],int low,int high){
if(low<high){
//找到基准点
int part = partition(a, low, high);
//将基准点前面的数在做排序
quickSort(a, low, part-1);
//将基准点后面的数在做排序
quickSort(a, part+1,high);
}
}
}
归并排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。
算法如下：
public class MergeSort {
public static void main(String[] args) {
int a[] = {1,5,3,4,5,8,10,21,4,5,1};
int b[] = new int[a.length];
mergeSort(a,b,0,a.length-1);
for(int i =0;i<b.length;i++){
System.out.print(b[i]+" ");
}
}
//合并 a的low到mid的有序数组，和mid到high的有序数组，合并成b
public static void merge(int a[],int b[],int low,int mid,int high){
int i = low,j=mid+1,k=low;
while(i<=mid&&j<=high){
if(a[i]<a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
}
while(i<=mid){
b[k++] = a[i++];
}
while(j<=high){
b[k++] = a[j++];
}
}
public static void mergeSort(int a[],int b[],int low,int high){
//s是中间数组
int s[] = new int[a.length];
if(low==high) b[low] = a[low];
else{
int mid = (low+high)/2;
mergeSort(a,s,low,mid);
mergeSort(a,s,mid+1,high);
merge(s,b,low,mid,high);
}
}
}
本文章是我这两天看过总结的java代码，有些话说的太白了，可能不易于理解，请大家见谅。
- 1楼HG_Rabbit昨天 17:45
- 赞！