您的位置: 首页  >  IT文章  >  常见排序算法与实现

常见排序算法与实现

分类: IT文章 • 2025-01-29 18:20:07

1.快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数。（基准数可以是第一个数，可以是中间的数，也可以是最后一个数）

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。（递归）

基准数 分区 递归

(left ,right,array[])

public static void quickSort(int a[], int start, int end)
{        int i,j;
         i = start;
         j = end;
         if((a==null)||(a.length==0))
             return;
         while(i<j){
             while(i<j&&a[i]<=a[j])     //以数组start下标的数据为key，右侧扫描
             j--;
             if(i<j){                   //右侧扫描，找出第一个比key小的，交换位置
                 int temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
             }
             while(i<j&&a[i]<a[j])    //左侧扫描（此时a[j]中存储着key值）
                 i++;
             if(i<j){                 //找出第一个比key大的，交换位置
                 int temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
             }
        }
        if(i-start>1){
             //递归调用，把key前面的完成排序
            quickSort(a,0,i-1);
        }
        if(end-j>1){
            quickSort(a,j+1,end);    //递归调用，把key后面的完成排序
        }
}
QuickSort

2.冒泡排序

例子：

/*
冒泡排序基本思想
将n个记录看作按纵向排列，每趟排序时自下至上对每对相邻记录进行比较，若次序不符合要求（逆序）就交换。每趟排序结束时都能使排序范围内关键字最小的记录象一个气泡一样升到表上端的对应位置，整个排序过程共进行n-1趟，依次将关键字最小、次小、第三小…的各个记录“冒到”表的第一个、第二个、第三个… 位置上。

   初态      第1趟   第2趟  第3趟   第4趟   第5趟   第6趟   第7趟
    38        12      12      12      12      12      12      12                              
    20        38      20      20      20      20      20      20
    46        20      38      25      25      25      25      25
    38        46      25      38      38      38      38      38
    74        38      46      38      38      38      38      38
    91        74      38      46      46      46      46      46
    12        91      74      74      74      74      74      74
    25        25      91      91      91      91      91      91
*/

import java.util.*;
public class DemoSort
{
public static void main(String args[]){

int arr1[]={1,5,3,0,-2,9};


//创建一个Bubble类
Bubble bubble=new Bubble();
bubble.sort(arr1);


//输出最后结果(在控制台输出非常消耗cpu)
for(int i=0;i<arr1.length;i++)
{
System.out.print(arr1[i]+" ");
}
}
}

//冒泡排序
class Bubble{
//排序方法
public void sort(int arr[]){

int temp=0;

//外层循环，决定它走几趟
for(int i=0;i<arr.length-1;i++)
{
//内层循环，开始逐个比较，如果发现前一个比后一个数大，则交换
for(int j=0;j<arr.length-1-i;j++) //-i是最大的数不参与比较了
{
if(arr[j]>arr[j+1]){
//换位
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
BubbleSort

3.插入排序

假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

像是玩樸克一樣，我們將牌分作兩堆，每次從後面一堆的牌抽出最前端的牌，然後插入前面一堆牌的適當位置，例如：    
排序前：92 77 67 8 6 84 55 85 43 67     
 1. [77 92] 67 8 6 84 55 85 43 67 將77插入92前 
2. [67 77 92] 8 6 84 55 85 43 67 將67插入77前     
3. [8 67 77 92] 6 84 55 85 43 67 將8插入67前     
4. [6 8 67 77 92] 84 55 85 43 67 將6插入8前     
5. [6 8 67 77 84 92] 55 85 43 67 將84插入92前     
6. [6 8 55 67 77 84 92] 85 43 67 將55插入67
7. [6 8 55 67 77 84 85 92] 43 67 ......     
8. [6 8 43 55 67 77 84 85 92] 67 ......     
9. [6 8 43 55 67 67 77 84 85 92] ......  

public class DemoSort
{
public static void main(String args[]){

int arr1[]={1,5,3,0,-2,9};

//创建一个InsertSort类
InsertSort ist=new InsertSort();
ist.sort(arr1);

//输出最后结果(在控制台输出非常消耗cpu)
for(int i=0;i<arr1.length;i++)
{
System.out.print(arr1[i]+" ");
}
System.out.println("
");
System.out.println("这是用插入排序");
}
}


class InsertSort
{
//插入排序方法
public void sort(int arr[])
{
for(int i=1;i<arr.length;i++)
{
int insertVal=arr[i];
//insertVal准备和前一个数比较
int index=i-1;
while(index>=0&&insertVal<arr[index])
{
//将把arr[index]向后移动
arr[index+1]=arr[index];
//让index向前移动
index--;
}
//将insertVal插入到适当位置
arr[index+1]=insertVal;
}
}
}
InsertSort

4.选择排序

    选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。不过条条大路通罗马，两者的目的是一样的。

public class DemoSort
{
public static void main(String args[]){

int arr1[]={1,5,3,0,-2,9};

//创建一个Select类
Select select=new Select();
select.sort(arr1);

//输出最后结果(在控制台输出非常消耗cpu)
for(int i=0;i<arr1.length;i++)
{
System.out.print(arr1[i]+" ");
}
System.out.println("
");
System.out.println("这是用选择排序");
}
}


//选择排序    找最小的和前面交换
class Select{
 public void sort(int arr[])
{
//我认为第一个数就是最小的
int temp=0;
for(int j=0;j<arr.length-1;j++)
{
int min=arr[j];
//记录最小数的小标
int minIndex=j;

for(int k=j+1;k<arr.length-1;k++)
{
if(min>arr[k])
{
//修改最小
min=arr[k];
minIndex=k;
}
}
//当退出for就找到这次的最小值
temp=arr[j];
arr[j]=arr[minIndex];
arr[minIndex]=temp;
}
}
}
SelectSort 
for(int i=0; i<v.size(); i++){
                int min = v[i]; 
                int temp;
                int index = i;
                for(int j=i+1;j<v.size();j++){
                    if(v[j] < min){ 
                        min = v[j]; 
                        index = j;
                    }       
                }       
        
                temp = v[i]; 
                v[i] = min;
                v[index]= temp;
        }

　　

相关推荐