排序算法和查找

绝地灬酷狼 2024-04-18 17:56 30阅读 0赞

排序和查找实例  
内部排序：交换式（冒泡、快速排序法）、选择式（选择、堆排序）、插入（插入、谢尔、二叉树）式排序  
外部排序：合并、直接合并排序

随机产生数组

public int[] getArray(int n){
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
                int t=(int)(Math.random()*1000000);
                arr[i]=t;
            }
            return arr;
        }

7.1冒泡法排序

//冒泡排序法
    class MaoPao{
        public void sort(int[] arr){
            int len=arr.length;
            int temp=0;
            for (int i=0;i<len-1;i++){
                for(int j=0;j<len-i-1;j++){
                   if (arr[j]>arr[j+1]){
                       temp=arr[j+1];
                       arr[j+1]=arr[j];
                       arr[j]=temp;
                   }
                }
            }
            for(int i=0;i<len;i++){
                System.out.println(arr[i]+" ");
            }
        } 
    }

7.2选择排序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70][]

//选择排序法
    class Xuanze{
        public void sort(int[] array){
            for(int i=0;i<array.length;i++){
                int min=i;
                int temp;
                for(int j=i;j<array.length;j++){
                    if(array[i]>array[j]){
                        min=j;
                    }
                }
                if(i!=min){
                    temp=array[min];
                    array[min]=array[i];
                    array[i]=temp;
                }
            } 
        }
    }

7.3插入排序  
 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 1][]

//插入排序
    class InsertSort{
        //插入排序
        public void sort(int arr[]){
            for(int i=1;i<arr.length;i++){
                int insertVal=arr[i];
                int index=i-1;
                while(index>=0&&insertVal<arr[index]){
                    arr[index+1]=arr[index];
                    index--;
                }
                arr[index+1]=insertVal;
            }
        }
    }

7.4快速排序（数据结构的递归）代码  
快速排序讲解：  
该方法的基本思想是：  
1．先从数列中取出一个数作为基准数。  
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。  
3．再对左右区间重复第二步，直到各区间只有一个数。

以一个数组作为示例，取区间第一个数为基准数。

![20190910114642483.png][]  
初始时，i = 0;  j = 9;   X = a\[i\] = 72  
由于已经将a\[0\]中的数保存到X中，可以理解成在数组a\[0\]上挖了个坑，可以将其它数据填充到这来。  
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a\[8\]挖出再填到上一个坑a\[0\]中。a\[0\]=a\[8\]; i++;  这样一个坑a\[0\]就被搞定了，但又形成了一个新坑a\[8\]，这怎么办了？简单，再找数字来填a\[8\]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a\[3\]挖出再填到上一个坑中a\[8\]=a\[3\]; j--;  
数组变为：

![20190910114652161.png][]  
i = 3;   j = 7;   X=72  
再重复上面的步骤，先从后向前找，再从前向后找。  
从j开始向前找，当j=5，符合条件，将a\[5\]挖出填到上一个坑中，a\[3\] = a\[5\]; i++  
从i开始向后找，当i=5时，由于i==j退出。  
此时，i = j = 5，而a\[5\]刚好又是上次挖的坑，因此将X填入a\[5\]。  
数组变为：  
 ![20190910114704271.png][]  
可以看出a\[5\]前面的数字都小于它，a\[5\]后面的数字都大于它。因此再对a\[0…4\]和a\[6…9\]这二个子区间重复上述步骤就可以了。

//快速排序法  
1.    //快速排序    
2.    void quick\_sort(int s\[\], int l, int r)    
3.    \{    
4.        if (l < r)  //注意此处是是否继续递归的分界点  
5.        \{    
6.            //Swap(s\[l\], s\[(l + r) / 2\]); //将中间的这个数和第一个数交换 参见注1    
7.            int i = l, j = r, x = s\[l\];  //注意:此处的赋值在if里面,否则可能出现outOfBoundException  
8.            while (i < j)    
9.            \{    
10.                while(i < j && s\[j\] >= x) // 从右向左找第一个小于x的数    
11.                    j--;      
12.                if(i < j)     
13.                    s\[i++\] = s\[j\];//先s\[i\]=s\[j\],再i++  
14.                    
15.                while(i < j && s\[i\] < x) // 从左向右找第一个大于等于x的数    
16.                    i++;      
17.                if(i < j)     
18.                    s\[j--\] = s\[i\];    
19.            \}    
20.            s\[i\] = x;    
21.            quick\_sort(s, l, i - 1); // 递归调用     
22.            quick\_sort(s, i + 1, r);    
23.        \}    
24.    \}

归并排序  
只有100M内存，怎么排序1G的数据？  
首先肯定不能使用内存排序算法，内存根本装不下，所以需要使用外存来排序。这时候使用多路归并排序，把数据分为n段，每段小于100Mb，再使用用内存来排序，将排序结果用外存记录，然后每次从外存中来取记录，在内存中进行比较，从而获取最后的排序结果

选堆排序法  
希尔排序法  
二叉树排序法

查找：  
顺序查找  
7.5各种排序算法的时间复杂度

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 2][]  
7.6二分查找

class BinaryFind{
        public void find(int leftIndex,int rightIndex,int val,int arr[]){
            //首先找到中间的值
            int midIndex=(rightIndex+leftIndex)/2;
            int midVal=arr[midIndex];
            int valIndex;
            
            //如果要找的数比midVal大
            if(midVal<val&&leftIndex<rightIndex){
                leftIndex=midIndex;
                System.out.println("not over  not found");
                find(rightIndex, leftIndex, val, arr);
            }else if(midVal>val&&leftIndex<rightIndex){
                rightIndex=midIndex;
                System.out.println("not over  not found");
                find(rightIndex, leftIndex, val, arr);
            }else if(midVal==val){
                valIndex=midIndex;
                System.out.println(valIndex+"found");
            }else{
                System.out.println("over but not found");
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4ef9e8835ae04f139475185437cc03a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d16a009e94924c899c27d37516246c72.png
[20190910114642483.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/35e83a2a087f442d93b4bbab3f2f86e5.png
[20190910114652161.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9680f81991ae4283a3d7eef1e6e27ef8.png
[20190910114704271.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a4de6e6c76734dfd96798026bc8e1d73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2gyNjA0Mzk2NzM5_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4e90c889f0674304aa276b9875661a7d.png