題目：給一組整數(shù)，按照升序排序，使用選擇排序，冒泡排序，插入排序或者任何 O(n2) 的排序算法

1、冒泡排序

? ? ?原理：從第一個整數(shù)開始第一趟，比較相鄰的兩個元素，大的放在后面；一輪結(jié)束后，最大的數(shù)沉底；重復這一過程，完整n-1趟。
? ? ?所以有兩個循環(huán)，外循環(huán)決定第幾趟、從第幾個元素開始比較；內(nèi)循環(huán)是比較相鄰兩個元素大小，決定要不要交換。 class Solution { public:/** @param A: an integer array* @return: */void sortIntegers(vector<int> &A){int temp = 0;if(A.size()!=0)//判斷是否為空數(shù)組{for(int i=0; i<A.size()-1; i++)//外循環(huán)只比較A.size()-1趟for(int j=i+1; j<A.size(); j++)//內(nèi)循環(huán)從i+1開始{if(A[i] > A[j]){temp = A[j];//交換A[j] = A[i];A[i] = temp;}}}} };

2、插入排序

? ? ?原理：第一趟把第一個元素當做有序序列，用第二個和第一個比，將大的放在后面；第二趟把前兩個元素當做有序序列，用第三個元素跟第二個比，大的放后面，再用第二個跟第一個比，大的放后面；第三趟把前三個當做有序序列，用第四個元素跟第三個比，再用第三個跟第二個比，第二個跟第一個比；......以此類推。兩個循環(huán)，外循環(huán)決定從無序序列開始，內(nèi)循環(huán)進行從后往前的兩兩比較和交換。 class Solution { public:/*** @param A an integer array* @return void*/void sortIntegers(vector<int>& A) {int temp = 0;for (int i = 1; i < A.size(); ++i) //從第二個元素開始{while (i > 0 && A[i] < A[i - 1])//當該元素前面還有元素，且比前面的數(shù)小，就進行下面的交換{temp = A[i];A[i] = A[i-1];A[i-1] = temp;--i;//遞減，往前比較}}} };

3、選擇排序

? ? ? 原理：遍歷整個數(shù)組，對于當前位置i，定義一個變量min_idx，用來記錄當前位置往后的最小的坐標，并通過遍歷以后所有的數(shù)字來找這個最小的坐標；然后交換A[i]和A[min_idx]。
? ? ? 外循環(huán)定義當前位置，內(nèi)循環(huán)找到當前往后最小的元素坐標。從第一個元素開始，選擇后面元素里面最小的一個和第一個元素交換，直到最后一個元素。

class Solution { public:/*** @param A an integer array* @return void*/void sortIntegers(vector<int>& A) { for (int i = 0; i < A.size(); ++i) {int min_idx = i;for (int j = i + 1; j < A.size(); ++j) {if (A[j] < A[min_idx]) {min_idx = j;}}swap(A[i], A[min_idx]);}} }; 參考： lintcode整數(shù)排序

? ? 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Lintcode--1(463)--整数排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。