数据结构中的排序和查找

末蓝、 2023-02-18 08:17 24阅读 0赞

# 数据结构中算法 #

## 选择排序 ##

### 简单选择排序 ###

private static void SelectionSort(int[] numbers, int length) {
        
        for (int i = 0; i < length - 1; i++) {
        
            int temp = i;
            for (int j = i + 1; j < length; j++)
                if (numbers[j] < numbers[temp]) temp = j;
            if (temp != i) Swap(numbers, i, temp);
        }
    }

### 堆排序 ###

/**
        * 选择排序-堆排序
        * @param array 待排序数组
        * @return 已排序数组
        */
        public static int[] heapSort(int[] array) {
        
            //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
            for (int i = array.length / 2 - 1; i >= 0; i--) {
          
                adjustHeap(array, i, array.length);  //调整堆
            }
      
            // 上述逻辑，建堆结束
            // 下面，开始排序逻辑
            for (int j = array.length - 1; j > 0; j--) {
        
                // 元素交换,作用是去掉大顶堆
                // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
                swap(array, 0, j);
                // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
                // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
                // 而这里，实质上是自上而下，自左向右进行调整的
                adjustHeap(array, 0, j);
            }
            return array;
        }
      
        /**
        * 整个堆排序最关键的地方
        * @param array 待组堆
        * @param i 起始结点
        * @param length 堆的长度
        */
        public static void adjustHeap(int[] array, int i, int length) {
        
            // 先把当前元素取出来，因为当前元素可能要一直移动
            int temp = array[i];
            for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
          //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
                // 让k先指向子节点中最大的节点
                if (k + 1 < length && array[k] < array[k + 1]) {
          //如果有右子树,并且右子树大于左子树
                    k++;
                }
                //如果发现结点(左右子结点)大于根结点，则进行值的交换
                if (array[k] > temp) {
        
                    swap(array, i, k);
                    // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                        i  =  k;
                            } else {
          //不用交换，直接终止循环
                    break;
                }
            }
        }
      
        /**
        * 交换元素
        * @param arr
        * @param a 元素的下标
        * @param b 元素的下标
        */
        public static void swap(int[] arr, int a, int b) {
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

## 交换排序 ##

### 冒泡排序 ###

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

### 快速排序 ###

public static int[] qsort(int arr[],int start,int end) {
                
        int pivot = arr[start];        
        int i = start;        
        int j = end;        
        while (i<j) {
                    
            while ((i<j)&&(arr[j]>pivot)) {
                        
                j--;            
            }            
            while ((i<j)&&(arr[i]<pivot)) {
                        
                i++;            
            }            
            if ((arr[i]==arr[j])&&(i<j)) {
                        
                i++;            
            } else {
                        
                int temp = arr[i];                
                arr[i] = arr[j];                
                arr[j] = temp;            
            }        
        }        
        if (i-1>start) arr=qsort(arr,start,i-1);        
        if (j+1<end) arr=qsort(arr,j+1,end);        
        return (arr);    
    }    
     
    public static void main(String[] args) {
                
        int arr[] = new int[]{
        3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};        
        int len = arr.length-1;        
        arr=qsort(arr,0,len);        
        for (int i:arr) {
                    
            System.out.print(i+"\t");        
        }    
    }

## 插入排序 ##

### 直接插入 ###

public class InsertSort{
        
         
        public void insertSort(int[] array){
        
            for(int i=1;i<array.length;i++)//第0位独自作为有序数列，从第1位开始向后遍历
            {
        
                if(array[i]<array[i-1])//0~i-1位为有序，若第i位小于i-1位，继续寻位并插入，否则认为0~i位也是有序的，忽略此次循环，相当于continue
                {
        
                    int temp=array[i];//保存第i位的值
                    int j = i - 1;
                    while(j>=0 && temp<array[j])//从第i-1位向前遍历并移位，直至找到小于第i位值停止
                    {
        
                        array[j+1]=array[j];
                        j--;
                    }
                    array[j+1]=temp;//插入第i位的值
                }
            } 
        }
         
        public static void printArray(int[] array) {
        
              for (int i = 0; i < array.length; i++) {
        
                   System.out.print(array[i]);
                   if (i != array.length - 1) {
        
                    System.out.print(",");
                   }
              }
         }
     
         
     
    }

### 折半插入 ###

public class MyBinaryInsertionSort
    {
        
    public static void main(String[] args)
    {
        
    // 待排序的数组
    int[] array = {
         1, 0, 2, 5, 3, 4, 9, 8, 10, 6, 7};
    binaryInsertSort(array);
    // 显示排序后的结果。
    System.out.print("排序后： ");
    for(int i = 0; i < array.length; i++)
    {
        
    System.out.print(array[i] + " ");
    }
    }
    // Binary Insertion Sort method
    private static void binaryInsertSort(int[] array)
    {
        
    for(int i = 1; i < array.length; i++)
    {
        
    int temp = array[i];
    int low = 0;
    int high = i - 1;
    while(low <= high)
    {
        
    int mid = (low + high) / 2;
    if(temp < array[mid])
    {
        
    high = mid - 1;
    }
    else
    {
        
    low = mid + 1;
    }
    }
    for(int j = i; j >= low + 1; j--)
    {
        
    array[j] = array[j - 1];
    }
    array[low] = temp;
    }
    }
    }

### 希尔排序 ###

public static void main(String[] args){
        
        int[] array={
        49,38,65,97,76,13,27,49,78,34,12,64,1};
            System.out.println("排序之前：");
            for(int i=0;i<array.length;i++){
        
                System.out.print(array[i]+" ");
            }
            //希尔排序
            int gap = array.length;
            while (true) {
            
                gap /= 2;   //增量每次减半    
                for (int i = 0; i < gap; i++) {
                
                    for (int j = i + gap; j < array.length; j += gap) {
        //这个循环里其实就是一个插入排序            
                        int temp = array[j];            
                        int k = j - gap;            
                        while (k >= 0 && array[k] > temp) {
                        
                            array[k + gap] = array[k];                
                            k -= gap;            
                        }            
                        array[k + gap] = temp;        
                    }    
                }    
                if (gap == 1)        
                    break;
            }
     
            System.out.println();
            System.out.println("排序之后：");
            for(int i=0;i<array.length;i++){
        
                System.out.print(array[i]+" ");
            }
        }