一、排序算法分類
1.外排序：需要在內外存之間多次交換數(shù)據(jù)
2. 內排序:只在內存中進行
- 插入排序類
- 直接插入排序
- 希爾排序
- 選擇排序類
- 簡單選擇排序
- 堆排序
- 交換類排序類
- 冒泡排序
- 快速排序
- 歸并排序類
- 歸并排序
希爾排序時直接插入排序的升級版，堆排序和快速排序分別是簡單選擇排序和冒泡排序的升級版。
- 歸并排序
二谓着、思想與實現(xiàn)
1.插入排序類
- 直接插入排序
思想：將一個記錄插入到已經(jīng)排好序的有序表中庶艾，從而得到一個新的、記錄數(shù)增加1的有序表
node.js實現(xiàn)
const readline=require('readline')
const rl=readline.createInterface({
input:process.stdin,
output:process.stdout
})
var arr=[]
rl.on('line',(input)=>{
arr=input.split(/\s+/).map((item)=>{
return +item
})
InsertSort(arr)
rl.close()
})
function InsertSort(arr){
const len=arr.length
for(let i=1;i<len;i++){
//如果即將插入的數(shù)比已排好序的最后一個數(shù)小屎蜓，已排好需要移動
if(arr[i]<arr[i-1]){
let temp=arr[i]
//對排好序的進行從后向前遍歷色解，一旦發(fā)現(xiàn)要插入的數(shù)值大于已排好序中的某個記錄茂嗓，停止，那么就找到了要插入的位置
for(var j=i-1;arr[j]>temp&&j>=0;j--){
//已排好序的記錄后移
arr[j+1]=arr[j]
}
//將要插入的數(shù)值插入
arr[j+1]=temp
}
}
console.log(arr)
}
- 希爾排序
思想：將相距某個’增量‘的記錄組成一個子序列科阎，在子序列內部進行直接插入排序述吸，當增量為1時，列表便有序了
//希爾排序，是直接插入排序的升級版
//思想將相距某個’增量‘的記錄組成一個子序列蝌矛，在子序列內部進行直接插入排序道批，當增量為1時，列表便有序了
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var inputArr = [];
rl.on('line', function (input) {
inputArr=input.split(/\s+/)
inputArr=inputArr.map((item)=>{
return +item
})
ShellSort(inputArr)
inputArr=[]
rl.close()
});
function ShellSort(arr){
var len=arr.length
if(len<1)return
var incement=len
while(incement>1){
incement=Math.ceil(incement/3)//增量序列
for(var i=incement;i<arr.length;i++){
//將arr[i]插入增量序列
if(arr[i]<arr[i-incement]){
var key=arr[i]
//向后看入撒，看的步長是incement隆豹，如果當前要插入的比前面的小，那么前面的需要后移
for(var j=i-incement;j>=0&&arr[j]>key;j-=incement){
arr[j+incement]=arr[j]
}
//直到要插入的比前面的大茅逮，找到位置插入
arr[j+incement]=key
}
}
}
console.log(arr)
}
2.選擇排序類
- 簡單選擇排序
思想：每趟從n-i（i=0,1,...n-1）個記錄中選出最小的那個關鍵字作為有序序列的第i個記錄
//簡單排序的思想：每趟從n-i（i=0,1,...n-1）個記錄中選出最小的那個關鍵字作為有序序列的第i個記錄璃赡。
const readline=require('readline')
const rl=readline.createInterface({
input:process.stdin,
output:process.stdout
})
var arr=[]
rl.on('line',(input)=>{
arr=input.split(/\s+/).map((item)=>{
return +item
})
SelectSort(arr)
rl.close()
})
function SelectSort(arr){
const len=arr.length
if (len<1)return
for(let i=0;i<len-1;i++){
let min=i
for(let j=i+1;j<len;j++){
if(arr[min]>arr[j]){
min=j
}
}
if(min!=i){
let t=arr[min]
arr[min]=arr[i]
arr[i]=t
}
}
console.log(arr)
}
- 堆排序
思想：將待排序列構造成一個大頂堆（小頂堆）。將根節(jié)點移走（與最后一個節(jié)點互換）献雅，對剩余的元素重新構造一個大頂堆碉考，然后再移走根節(jié)點，如此反復挺身。
//堆排序算法思想
//將待排序列構造成一個大頂堆（小頂堆）侯谁。將根節(jié)點移走（與最后一個節(jié)點互換），對剩余的元素重新構造一個大頂堆章钾，然后再移走根節(jié)點墙贱，如此反復。
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var inputArr = [];
rl.on('line', function (input) {
inputArr=input.split(/\s+/)
inputArr=inputArr.map((item)=>{
return +item
})
HeapSort(inputArr)
inputArr=[]
rl.close()
});
function HeapSort(arr){
var len=arr.length
if(len<1)return
//建堆
for(let i=Math.floor(len/2)-1;i>=0;i--){
HeapAdjust(arr,i,len-1)
}
//交換第一個和最后一個伍玖，調整堆
for(let i=len-1;i>0;i--){
swap(arr,0,i)
HeapAdjust(arr,0,i-1)
}
console.log(arr)
}
//adjnum需要調整的下標,len最大下標（總長度-1）
//調整arr[adjnum],使得[adjnum,len]為大頂堆
function HeapAdjust(arr,adjnum,len){
var temp=arr[adjnum]
for(var j=2*adjnum+1;j<=len;j=j*2+1){
if(j<len&&arr[j]<arr[j+1]){
j++//j是較大關鍵字的下標
}
if(temp>arr[j]){
break
}
arr[adjnum]=arr[j]//較大關鍵字放在父親節(jié)點上
adjnum=j
}
arr[adjnum]=temp//相當于最大點和父親節(jié)點交換
}
function swap(arr,low,high){
var t=arr[low]
arr[low]=arr[high]
arr[high]=t
}
3.交換排序類
- 冒泡排序
思想：兩兩比較相鄰記錄
法一
// 冒泡排序的思想嫩痰，兩兩比較相鄰記錄
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var inputArr = [];
rl.on('line', function (input) {
inputArr=input.split(/\s+/)
inputArr=inputArr.map((item)=>{
return +item
})
BubbleSort(inputArr);
inputArr=[]
rl.close()
});
function BubbleSort(list_num){
let len=list_num.length
if (len<1)
return
for(let i=0;i<len;i++){
for(let j=len-1;j>i;j--){
if(list_num[j]<list_num[j -1]){
let t=list_num[j];
list_num[j]=list_num[j-1];
list_num[j-1]=t;
}
}
}
console.log(list_num)
// rl.write(list_num.join(' '));write第一個參數(shù)表示輸出的數(shù)據(jù)剿吻，必須是字符串類型
}
法二
// 冒泡排序的思想窍箍，兩兩比較相鄰記錄
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var inputArr = [];
rl.on('line', function (input) {
inputArr=input.split(/\s+/)
inputArr=inputArr.map((item)=>{
return +item
})
BubbleSort(inputArr);
inputArr=[]
rl.close()
});
function BubbleSort(list_num){
let len=list_num.length
let flag=true
if (len<1)
return
for(let i=0;i<len&&flag;i++){
flag=false
for(let j=len-1;j>i;j--){
if(list_num[j]<list_num[j -1]){
let t=list_num[j];
list_num[j]=list_num[j-1];
list_num[j-1]=t;
flag=true
}
}
}
console.log(list_num)
// rl.write(list_num.join(' '));write第一個參數(shù)表示輸出的數(shù)據(jù)，必須是字符串類型
}
- 快速排序
思想：通過一趟排序丽旅，將待排記錄分割成獨立的兩部分椰棘，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序榄笙，已達到整個序列有序的目的
法一
//快速排序的思想
//通過一趟排序邪狞，將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小茅撞，
//則可分別對這兩部分記錄繼續(xù)進行排序帆卓，已達到整個序列有序的目的
const readline=require('readline')
const rl=readline.createInterface({
input:process.stdin,
output:process.stdout
})
var arr=[]
rl.on('line',(input)=>{
arr=input.split(/\s+/).map((item)=>{
return +item
})
QuickSort(arr)
// Partition(arr,0,arr.length-1)
rl.close()
})
//對整個序列進行快速排序
function QuickSort(arr){
Qsort(arr,0,arr.length-1)
console.log(arr)
}
//對[low...high]之間的序列進行快速排序
function Qsort(arr,low,high){
if(low<high){
var pivot=Partition(arr,low,high)//將arr[low..high]一分為二，返回一分為二的樞紐所在位置
Qsort(arr,pivot+1,high)//對高子遞歸表排序
Qsort(arr,low,pivot-1)//對低子遞歸表排序
}
}
function Partition(arr,low,high){
var pivotkey=arr[low]
while(low<high){
while(low<high&&arr[high]>pivotkey)
high--
swap(arr,low,high)
while(low<high&&arr[low]<pivotkey)
low++
swap(arr,low,high)
}
return low
// console.log(arr)
}
function swap(arr,low,high){
var t=arr[low]
arr[low]=arr[high]
arr[high]=t
}
法二
//快速排序的思想
//通過一趟排序米丘，將待排記錄分割成獨立的兩部分剑令，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，
//則可分別對這兩部分記錄繼續(xù)進行排序拄查，已達到整個序列有序的目的
//優(yōu)化：1吁津、樞紐關鍵字選取，使用左中右取三者中間值作為關鍵字樞紐堕扶。2碍脏、減少不必要的交換梭依，使用替換
//對于小數(shù)組，使用直接插入排序會更高
const readline=require('readline')
const rl=readline.createInterface({
input:process.stdin,
output:process.stdout
})
var arr=[]
rl.on('line',(input)=>{
arr=input.split(/\s+/).map((item)=>{
return +item
})
QuickSort(arr)
// Partition(arr,0,arr.length-1)
rl.close()
})
//對整個序列進行快速排序
function QuickSort(arr){
Qsort(arr,0,arr.length-1)
console.log(arr)
}
//對[low...high]之間的序列進行快速排序
function Qsort(arr,low,high){
if(low<high){
var pivot=Partition(arr,low,high)//將arr[low..high]一分為二典尾，返回一分為二的樞紐所在位置
Qsort(arr,pivot+1,high)//對高子遞歸表排序
Qsort(arr,low,pivot-1)//對低子遞歸表排序
}
}
function Partition(arr,low,high){
//優(yōu)化關鍵字樞紐役拴，將中間值賦給arr[low]
var m=low+parseInt((high-low)/2)
if(arr[low]>arr[high])
swap(arr,low,high)
if(arr[m]>arr[high])
swap(arr,m,high)
if(arr[m]>arr[low])
swap(arr,m,low)
//此時low已經(jīng)是三者的中間值了
var pivotkey=arr[low]
var temp=pivotkey//備份中間樞紐
while(low<high){
while(low<high&&arr[high]>pivotkey)
high--
arr[low]=arr[high]
while(low<high&&arr[low]<pivotkey)
low++
arr[high]=arr[low]
}
arr[low]=temp
return low
// console.log(arr)
}
function swap(arr,low,high){
var t=arr[low]
arr[low]=arr[high]
arr[high]=t
}
4.歸并排序類
- 歸并排序
思想：把原序列分成兩個長度為n/2的子序列，對這兩個子序列分別進行歸并排序急黎，最后把兩個排好序的子序列合并成一個最終的派系序列
//歸并排序
//把原序列分成兩個長度為n/2的子序列扎狱，對這兩個子序列分別進行歸并排序，最后把兩個排好序的子序列合并成一個最終的派系序列
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
var arr = []
rl.on('line', (input) => {
arr = input.split(/\s+/).map((item) => {
return +item
})
console.log(MergeSort(arr))
// Partition(arr,0,arr.length-1)
rl.close()
})
function MergeSort(arr) {
var len = arr.length;
if (len < 2) return arr //遞歸勃教，當長度為1時此處必須返回arr淤击，然后再逐層合并
var middle = Math.floor(len / 2),
l = arr.slice(0, middle),
r = arr.slice(middle);
return merge(MergeSort(l), MergeSort(r))
// console.log(x)
}
function merge(l,r){
var result=[]
while(l.length&&r.length){
if(l[0]<=r[0]){
result.push(l.shift())
}else{
result.push(r.shift())
}
}
if(l.length){
result.concat(l)
}
if(r.length){
result.concat(r)
}
return result
}
三、復雜度及穩(wěn)定性
四故源、注意事項
編程要考慮全面污抬，首先判斷輸入的參數(shù)是否是空，再者如果不確定輸入的類型绳军，要做類型檢測
參考資料
大話數(shù)據(jù)結構-程杰著
