数据结构之基础入门八(二.交换排序)

绝地灬酷狼 2022-11-30 12:44 164阅读 0赞

### 数据结构.基础入门.交换排序.考研复习.面试算法练习 ###

*  0. 目录
 *  8. 排序
 *   *  8.2 交换排序
     *   *  8.2.1 冒泡排序
         *  8.2.2 快速排序

# 0. 目录 #

# 8. 排序 #

## 8.2 交换排序 ##

### 8.2.1 冒泡排序 ###

typedef int ElemType;
    
    void BubbleSort(ElemType A[], int n)
    {
        bool flag;
        for (int i = 0; i < n - 1; i++)
        {
            flag = false;                   //表示本趟冒泡是否发生交换的标志
            for (int j = n - 1; j > i; j--) //一趟冒泡
            {
                if (A[j - 1] > A[j]) //若为逆序
                {
                    swap(A[j - 1], A[j]); //交换
                    flag = true;
                }
            }
            if (flag == false) //本趟遍历后没有发生交换,说明已经有序
            {
                return;
            }
        }
    }

下面也提供可运行的Java版本源码,还原每一次冒泡的过程:

import java.util.Scanner;
    
    //冒泡排序-Java
    public class Sort{
        private static int data[]={12,10,6,7,3,16,9};
    
        public static void input() {
            Scanner scanner=new Scanner(System.in);
            System.out.println("请输入10个排序的数据: ");
    
            for(int i=1;i<data.length;i++){
                data[i]=scanner.nextInt();
            }   
        }
    
        public static void bubbleSort(int array[]) {
            boolean flag=false;
    
            for(int i=0;i<array.length-1;i++){
                flag=false;
    
                for(int j=array.length-1;j>i;j--){
                    if(array[j-1]>array[j]){
                        int temp=array[j-1];
                        array[j-1]=array[j];
                        array[j]=temp;
                        flag=true;
                    }
                }
    
                if(flag==false){
                    return;
                }
                output();
            }
        }
    
        protected static void output(){
            System.out.println("顺序为:");
            for(int i=0;i<data.length;i++){
                System.out.print(data[i]+" ");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            //input();
            output();
            bubbleSort(data);
            output();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ3MzIyOA_size_16_color_FFFFFF_t_70_pic_center]

### 8.2.2 快速排序 ###

typedef int ElemType;
    
    void QuickSort(ElemType A[], int low, int high)
    {
        if (low < high) //递归跳出的条件
        {
            //Partition()就是划分操作,将表A[low...high]划分为满足上述条件的两个子表
            int pivotpos = Partition(A, low, high); //划分
            QuickSort(A, low, pivotpos - 1);        //依次对两个子表进行递归排序
            QuickSort(A, pivotpos + 1, high);
        }
    }
    
    int Partition(ElemType A[], int low, int high) //一趟划分
    {
        ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴,对表进行划分
        while (low < high)       //循环跳出条件
        {
            while (low < high && A[high] >= pivot)
            {
                --high;
            }
            A[low] = A[high]; //将比枢轴小的元素移动到左端
            while (low < high && A[low] <= pivot)
            {
                ++low;
            }
            A[high] = A[low]; //将比枢轴大的元素移动到右端
        }
        A[low] = pivot  //枢轴元素存放到最终位置
            return low; //返回存放枢轴的最终位置
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ3MzIyOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c84745c5907144a3b90482cda6806282.png