- 冒泡排序 Bubble Sort
- 选择排序 Selection Sort
- 计数排序 Counting Sort
- 桶排序 Bucket Sort
- 堆排序 Heap Sort
- 基数排序
1.冒泡排序
两两摸头法
- 伪代码：
a <- {
'0':6,
'1':3,
'2':7,
'3':11,
'4':4,
'5':9,
'length':6
}
轮数n <- 1
while (n < a['length'])
选中的数字的下标i <- 0
while (i < a['length'] - n)
if (a[i] < a[i+1])
i <- i+1
else
t <- a[i]
a[i] <- a[i+1]
a[i+1] <- t
i <- i+1
end
n <- n+1
end
end
-
流程图
冒泡排序法.png
2.选择排序法
一指禅法
- 伪代码
a <- {
'0':3,
'1':5,
'2':1,
'3':7,
'4':2,
'5':6,
'length':6
}
轮数n <- 1
while (n < a['length'])
minIndex <- n-1
index <- minIndex+1
while (index < a['length'])
if(a[minIndex] < a[index])
index <- index+1
else
minIndex <- index
index <- index+1
end
t <- a[n-1]
a[n-1] <- a[minIndex]
a[minIndex] <- t
index <- index+1
end
print a
end
-
流程图
选择排序法.png
3.计数排序法
Hash当桶
- 伪代码
a <- {
'0':0,
'1':5,
'2':1,
'3':7,
'4':2,
'5':5,
'length':6
}
hash <- {
}
//入桶
index <- 0
while (index < a['length'])
number <- a['index']
if hash[number] == undefined
hash[number] <- 1
else
hash[number] <- hash[number] + 1
end
index <- index + 1
end
//出桶
index2 <- 0
//确定hash长度（最大的数+1）
max <-findMax(a)
/*
findMax(a):
index3 <- 0
max <- a['index3']
while(index3 < a['length']-1)
if(a['index3'] < a['index3'+1])
max <- a['index3'+1]
else
max <- a['index3']
index3 <- index3+1
end
*/
while(index2 < max+1)
count <- hash[index2]
if count != undefined
countIndex <- 0
while(countIndex < count)
newArr.push(index2)
countIndex <- countIndex+1
end
end
index2 <- index2+1
print newArr
end
-
流程图
计数排序法.png
4.桶排序
- 伪代码
a <- {
'0':0,
'1':5,
'2':1,
'3':7,
'4':2,
'5':5,
'length':6
}
hash <- {
}
//入桶
capacity <- 10 //每个桶存放的数字范围
findMaxMin(a): //找出数组a中最大值和最小值
index3 <- 0
max <- a['index3']
min <- a['index3']
while(index3 < a['length']-1)
if(a['index3'] > max)
max <- a['index3']
if(a['index3'] < min)
min <- a[index3]
index3 <- index3+1
end
bucketCount <- 取整[(max-min)/capacity] //确定桶的数量
index <- 0
while(index < a['length'])
bucketIndex <- 0
while(bucketIndex < bucketCount)
if a[index] <= (min+capacity*(bucketIndex+1)) && a[index] > (min+capacity*bucketIndex)
if(bucket[bucketIndex] == undefined)
bucket[bucketIndex] <- []
else
bucket[bucketIndex].push(a[index])
end
end
bucketIndex <- bucketIndex+1
end
index <- index+1
end
//用冒泡排序将桶内数据排序
轮数n <- 1
while (n < bucketIndex)
minIndex <- n-1
index <- minIndex+1
while (index < bucketIndex)
if(bucket[bucketIndex][minIndex] < bucket[bucketIndex][index])
index <- index+1
else
minIndex <- index
index <- index+1
end
t <- bucket[bucketIndex][n-1]
bucket[bucketIndex][n-1] <- bucket[bucketIndex][minIndex]
bucket[bucketIndex][minIndex] <- t
index <- index+1
end
end
//出桶
outBucket <- 0
while(outBucket < bucketCount)
if bucket[outBucket] != undefined
outBucketIndex <- 0
while(outBucketIndex < bucket[outBucket].length)
newArr.push(bucket[outBucket][outBucketIndex])
end
outBucket <- outBucket+1
end
print newArr
end
-
流程图
桶排序.png
5.堆排序
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
- 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
- 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
