偶遇排序算法

妖狐艹你老母 2022-09-12 03:50 31阅读 0赞

## 一、选择排序 ##

1.  `java`选择排序示例

/** * Describe : java选择排序 */
    import java.util.Arrays;
    
    public class Sort { 
        public static void main(String[] args) { 
            int[] arr = {  2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5 };
            for (int i = 0, index = 0; i < arr.length; i++, index++) { 
                int min = arr[index];
                int minIndex = index;
                for (int j = index + 1; j < arr.length; j++) { 
                    if (min > arr[j]) { 
                        min = arr[j];
                        minIndex = j;
                    }
                }
                int temp = arr[index];
                arr[index] = min;
                arr[minIndex] = temp;
            }
            Arrays.toString(arr)
        }
    }

1.  `C++`选择排序示例

/** * Describe : C++选择排序 */
    #include <iostream>
    #include <vector>
    using namespace std;
    int main()
    { 
        vector<int> arr = { 2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5};
        for (int i = 0, index = 0; i < arr.size(); i++, index++)
        { 
            int min = arr[index];
            int minIndex = index;
            for (int j = index + 1; j < arr.size(); j++)
            { 
                if (min > arr[j])
                { 
                    min = arr[j];
                    minIndex = j;
                }
            }
            int temp = arr[index];
            arr[index] = min;
            arr[minIndex] = temp;
        }
        for (int i : arr)
        { 
            cout << i << ' ';
        }
    }

## 二、冒泡排序 ##

1.  `java`冒泡排序示例

import java.util.Arrays;
    
    /** * Describe : java冒泡排序 */
    public class BubbleSort { 
        public static void main(String[] args) { 
            int[] arr = {  2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5 };
            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;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

1.  `C++`冒泡排序示例

/** * Describe : C++冒泡排序 */
    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    { 
        vector<int> arr = { 2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5};
        for (int i = 0; i < arr.size() - 1; i++)
        { 
            for (int j = 0; j < arr.size() - 1 - i; j++)
            { 
                if (arr[j] > arr[j + 1])
                { 
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    
        for (int i : arr)
        { 
            cout << i << ' ';
        }
    }

## 插入排序 ##

1.  `java`插入排序示例

import java.util.Arrays;
    
    /** * Describe : Java插入排序 */
    public class InsertSort { 
        public static void main(String[] args) { 
            int[] arr = {  2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5 };
    
            for (int index = 1; index < arr.length; index++) { 
                // 当前开始插入第几个
                int current = arr[index];
                // 从当前的数往前找，在到达0索引前找大于或等于当前的数的索引
                int pos = index;
                while (pos > 0 && current < arr[pos - 1]) { 
                    // 比当前的大的，都放到当前的后边
                    arr[pos] = arr[pos - 1];
                    pos--;
                }
                arr[pos] = current;
            }
            System.out.println(Arrays.toString(arr));
        }
    }

1.  `C++`插入排序示例

/** * Describe : C++插入排序 */
    #include <iostream>
    #include <vector>
    using namespace std;
    int main()
    { 
        vector<int> arr = { 2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5};
    
        for (int index = 1; index < arr.size(); index++)
        { 
            // 当前开始插入第几个
            int current = arr[index];
            // 从当前的数往前找，在到达0索引前找大于或等于当前的数的索引
            int pos = index;
            while (pos > 0 && current < arr[pos - 1])
            { 
                // 比当前的大的，都放到当前的后边
                arr[pos] = arr[pos - 1];
                pos--;
            }
            arr[pos] = current;
        }
        for (int i : arr)
        { 
            cout << i << ' ';
        }
        return 0;
    }

## 快速排序 ##

1.  `java`快速排序示例

import java.util.Arrays;
    
    /** * Describe : C++快速排序 */
    
    public class SpeadSort { 
        static int[] arr = {  2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5 };
    
        /** * @brief 划区调整，以每个区的第一个元素为基准元素，把比最初的第一个元素小的，全放到左边 * * @param left 左边界 * @param right 右边界（不计） * @param arr 数组 */
        static void f(int left, int right) { 
            // 当右边界只比左边界大1时，不需要进行调整
            if (left >= right - 1) { 
                return;
            }
            // 最初的左边界索引，基准数值索引
            int baseIndex = left;
            for (int i = left + 1; i < right; ++i) { 
                // 比基准数值小的放到基准数值左边
                if (arr[baseIndex] > arr[i]) { 
                    int temp = arr[i];
                    int tempIndex = i;
                    while (tempIndex != baseIndex) { 
                        arr[tempIndex] = arr[tempIndex - 1];
                        tempIndex--;
                    }
                    arr[baseIndex] = temp;
                    // 此时的基准数值已经左移了1
                    baseIndex++;
                }
            }
            // 调整完成后左部分进行调整
            f(left, baseIndex);
            // 调整完成后右部分进行调整
            f(baseIndex + 1, right);
        }
    
        public static void main(String[] args) { 
            f(0, arr.length);
            System.out.println(Arrays.toString(arr));
        }
    
    }

1.  `C++`快速排序示例

/** * Describe : C++快速排序 */
    
    #include <iostream>
    #include <vector>
    using namespace std;
    /** * @brief 划区调整，以每个区的第一个元素为基准元素，把比最初的第一个元素小的，全放到左边 * * @param left 左边界 * @param right 右边界（不计） * @param arr 数组 */
    void f(int left, int right, vector<int> &arr)
    { 
        // 当右边界只比左边界大1时，不需要进行调整
        if (left >= right - 1)
        { 
            return;
        }
        //最初的左边界索引，基准数值索引
        int baseIndex = left;
        for (int i = left + 1; i < right; ++i)
        { 
            //比基准数值小的放到基准数值左边
            if (arr[baseIndex] > arr[i])
            { 
                int temp = arr[i];
                int tempIndex = i;
                while (tempIndex != baseIndex)
                { 
                    arr[tempIndex] = arr[tempIndex - 1];
                    tempIndex--;
                }
                arr[baseIndex] = temp;
                //此时的基准数值已经左移了1
                baseIndex++;
            }
        }
        // 调整完成后左部分进行调整
        f(left, baseIndex, arr);
        // 调整完成后右部分进行调整
        f(baseIndex + 1, right, arr);
    }
    
    int main()
    { 
        vector<int> arr = { 2, 5, 4, 6, 1, 2, 3, 6, 9, 4, 8, 5};
        f(0, arr.size(), arr);
        for (int i : arr)
        { 
            cout << i << ' ';
        }
        return 0;
    }

[个人博客][Link 1]:`https://www.blog.hiyj.cn/admin/#/article/edit/111`

[Link 1]: https://www.blog.hiyj.cn/admin/#/article/edit/111